Hola!
Ya lo tengo de nuevo, completo, con especificación algebraica, implementación, programa principal y todo! (no se pedía todo)
Como esto es un foro de C/C++ , empezamos por el final, la implementación... Tened en cuenta que sólo se pedía el struct y la operación equals (Mismo Ciclo). Me ha salido más fácil que ayer!!
/*
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
)))) {
};
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;
}
}
Y algunos casos de prueba emepzando por los de la foto.
Protocolo de entrada.
- 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
Protocolo de salida: 1 marca TRUE ( permutaciones ciclicas equivalentes) 0 marca FALSE
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
Otros casos que no tienen que ver con esos.
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
y Ahora.... Para los que busquen algo "pure mathematical", sin C... aquí os dejo la especifiación ecuacional del tipo Ciclic... No se si tiene fallos...
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))
Y unos breves apuntes sobre la implementación, expresando el invariante de representación y la función de abstracción.
A lo mejor estas cosas no parecen imporantes, pero sirven para guiarme en como hago las cosas luego en C.
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)] )
Autor
En línea
.
