Foro de elhacker.net

#define MAX 10000
#include <assert.h>
 
/* Static memory implementation */
 
typedef struct {
  int V[MAX];
  int N;
} CycleSeq, *pCycleSeq;
 
 
/* Comment: Compare cannonical forms */
int SameCycle(CycleSeq *A, CycleSeq *B)
{
 
  if (A->N != B->N) return 0;
 
  if (A->N == 0 ) return 1 ;
 
  // otherwise
  assert((A->N == B->N) && A->N );
 
  int n ;
  int mA, mB;
  for (mA=mB=0, n = 1 ; n < A->N ; n++)
    {
      if (A->V[mA]>A->V[n]) mA = n ;
      if (B->V[mB]>B->V[n]) mB = n ;
    };
  // mA mB holds minimum positions; 
 // count coincidences in cannonical form.
  int count;
  for(count=0; (count < A->N) && (A->V[mA]==B->V[mB]); mA=(mA+1)% A->N,mB=(mB+1)%A->N  )
    count++;
  return count == A->N;
}

/*
CYCLE: Informally, a circular permutation, ie.
 
  [1,4,23,7]~[4,23,7,1]~[23,7,1,4]~[7,1,4,23]
*/
#define MAX 10000
#include <cassert>
#include <cstdlib>
#include <cstdio>
 
// Implementation on static memory.
typedef struct {
  int V[MAX];
  int N;
} CycleSeq, *pCycleSeq;
 
CycleSeq* cycle(const int V[],const int N)
{
  // Pre: assumed Def(canonical(V))
  CycleSeq *A;
  if (!(A = (pCycleSeq)malloc(sizeof(CycleSeq))))
    {
      perror("malloc");
      exit(1);
    };
  A->N = N ; 
  for(int n=0; n<N ; n++) A->V[n]=V[n];
  return A;
}
 
int contains(const int i,const CycleSeq *A)
{
  // Pre: true O(n)
  int n;
  for (n=0 ; n<A->N && (A->V[n]!=i) ; n++);
  return (n<A->N);
 
}
 
int next(const int i,const CycleSeq *A)
{
  // Pre: contains(A,i) O(n)
  int n ;
  for ( n=0 ; A->V[n]!=i ; n++);
  return (A->V[(n+1)%A->N]);
 
}
 
/* Comment: Compare cannonical forms . (Was SameCycle)*/
int equals(const CycleSeq *A, const CycleSeq *B)
{
 
  if (A->N != B->N) return 0;
 
  if (A->N == 0 ) return 1 ;
 
  // e.o.c
  assert((A->N == B->N) && A->N );
 
  int n ;
  int mA, mB;
  for (mA=mB=0, n = 1 ; n < A->N ; n++)
    {
      if (A->V[mA]>A->V[n]) mA = n ;
      if (B->V[mB]>B->V[n]) mB = n ;
    };
  // mA mB holds minimum positions; count matches in cannonical form.
  for(n=0; (n < A->N) && (A->V[(mA+n)%A->N]==B->V[(mB+n)%A->N]); n++);
  return (n == A->N);
}
 
#include <iostream>
using namespace std;
#define MAX 10000
 
int main(int argc, char *args[])
{
  CycleSeq *B,*A;
  int V1[MAX],V2[MAX];
  int N1,N2;
  for( ; cin >> N1 && cin >>N2 ; )
    {
      for(int n=0; n<N1; n++) cin >> V1[n];
      for(int n=0; n<N2; n++) cin >> V2[n];
      A= cycle(V1,N1);
      B= cycle(V2,N2);
      cout << equals(A,B) << endl;
      free(A);
      free(B);
    }
}

• Linea que marca la longitud de las permutaciones ciclicas
• Componentes de la primera permucacion
• Componentes de la segunda permucacion
• Acaba cuando no se dan pares de longitudes

5 5
6 23 4 71 9
71 9 6 23 4
1
5  5
71 9 6 23 4
6 23 4 71 9
1
5  5
6 23 4 71 9
6 23 71 4  9
0

1 1 
3 3 
1
1 1
3 4
0
2 2
1 2
2 1
1
2 3 
1 2 
1 2 3
0
4 4
1 4 23 7 
4 23 7 1
1
4  4
4 23 7 1
23 7 1 4
1
4  4
23 7 1 4
7 1 4 23
1
4  4
7 1 4 23
1 4 23 7
1
4  4
1 4 23 7
23 7 1 4 
1
4 4 
23 7 1 4 
23 1 7 4
0

 CYCLE: Informally, a circular permutation, ie.

  [1,4,23,7]~[4,23,7,1]~[23,7,1,4]~[7,1,4,23]


  Algebraic Spec: 
  ---------------

  TAD CYCLE is

  uses SEQ;

  carrier Cycle;

  ops
  ---

  cycle : Seq -> Cycle   [non free cons]

  partial next : Int Cycle -> Int   [ obs ]

  aux ops 
  --------

  contains : Int Cycle -> Bool  [obs]

  partial canonical  : Seq -> Seq  // extends TAD SEQ, but safe

  var
  ---
  n:Int, c:Cycle , s: Seq

  axioms
  ------

  contains(n,c) -> Def(next(n,c))

  nonRepeated(s) -> Def(canonical(s))

  Def(canonical(s)) -> Def(cycle(s))

  contains(n,cycle(s)) = contains(n,s)

  // canonical form of a a seq.
 length(s) = length(cannonical(s))

  let
    M = length(s)
  in
    (M==0 ||
           let 
              ms,ms' = min(s) , min(canonical(s))
           in  
           \forall i : 0<= i < M : s.at[(ms+i)%M]=cannonical(s).at[(ms'+i)%M])

  cycle(seq) = cycle(cannonical(seq))  

  Impl:
  -----

    int V[MAX];
    int N;

  INV : N<=MAX && \forall : 0 <= i < N : frec(V[i],V)=1 

  ABSTRACTION : (V1,N1) ~ (V2,N2)

     N1=N2 and
     (N1 = 0 ||
     let A = min i : 0 <= i < N1 : V1[i]
         B = min i : 0 <= i < N2 : V2[i]
     in
     \forall : 0 <= i < N1 : V1[(A+i) mod N1)] = V2[(B+i) mod N1)] )