Permutations dans un jeu de 32 cartes

Version imprimable

Voir 40 message(s) de cette discussion en une page

04/07/2007, 23h45
Zavonen

Citation:

@Zavonen : je crois qu'on ne permute pas de la même manière :

Je pense que cela n'a pas d'importance ...
du moins pour ce qui nous préoccupe actuellement (périodicité)

Salut !

Il y a une différence quand même !
Exemple avec N = 8 et K = 9

a) La méthode semblant celle du problème (donc celle que j'applique) :

Code:

1
2
3
4
5
6
7
8
9
10
0 - 1 2 3 4 5 6 7 8 << état initial 
1 - 5 1 6 2 7 3 8 4 
2 - 7 5 3 1 8 6 4 2 
3 - 8 7 6 5 4 3 2 1 
4 - 4 8 3 7 2 6 1 5 
5 - 2 4 6 8 1 3 5 7 << pairs | impairs dont l'entrelacement redonne...
6 - 1 2 3 4 5 6 7 8 << état initial
7 - 5 1 6 2 7 3 8 4 
8 - 7 5 3 1 8 6 4 2 
9 - 8 7 6 5 4 3 2 1

b) Ta méthode :

Code:

1
2
3
4
5
6
7
8
9
10
0 - 1 2 3 4 5 6 7 8 << état initial 
1 - 1 5 2 6 3 7 4 8 
2 - 1 3 5 7 2 4 6 8 << impairs | pairs dont l'entrelacement redonne... 
3 - 1 2 3 4 5 6 7 8 << état initial
4 - 1 5 2 6 3 7 4 8 
5 - 1 3 5 7 2 4 6 8 
6 - 1 2 3 4 5 6 7 8 << état initial
7 - 1 5 2 6 3 7 4 8 
8 - 1 3 5 7 2 4 6 8 
9 - 1 2 3 4 5 6 7 8 << état initial

A plus !

05/07/2007, 12h13
acx01b

salut

http://www.research.att.com/~njas/se...nguage=english

c'est marrant:

si on numérote de 0 à N-1 les cartes et quelque soit N pair
si k < N/2:
k -> 2k + 1
si k >= N/2:
k -> (k - N/2) * 2

on a donc dans tous les cas
k -> (2k+1) % (N+1)
on a donc avec position de départ k
U(0) = k
U(n+1) = (2Un+1) % (N+1)

et on cherche le plus petit n différent de 0 tel que pour tout k
U(0) = U(n) = k

on a
U(n+1) = (k*2^n + 2^n - 1)%(N+1)
si k = 0 il faut donc que pour la solution n on ait
U(0) = U(n) = (2^n-1) % (n+1) = 0
et si
(2^n-1) % (n+1) = 0
on a (k*2^n + 2^n - 1)%(n+1) = k
donc c'est gagné
la solution c'est le plus petit n tel que N+1 divise 2^n - 1

EDIT: comment on fait pour N impair ?? :)
05/07/2007, 12h55
Zavonen

Citation:

Envoyé par henderson

Salut !

Il y a une différence quand même !
Exemple avec N = 8 et K = 9

A plus !

Oui, c'est la surprise du chef ! car en pratique ça revient à inverser le tas de droite et le tas de gauche.
Faut dire que sur l'image de Pseudocode on ne voit pas très bien (zoom sur la première carte svp)
Bon ! on va essayer de tirer ça au clair (enfin pas tout).
C'est vu !
Dans mon tableau ça décale tous les nombres d'un cran vers la gauche, parce que dans mon système la première et la dernière carte ne bougent pas, donc ma méthode avec n+2 cartes = ta méthode avec n cartes.

Salut !

Sinon, il y a une méthode récursive.
Avec BCB (C++), voici ce que ça donne (pour ce que j'ai pu tester ça semble bien fonctionner) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int Calculer(int J, int H, int K)
{
int j=J;
if(K > 0)
    {
    if(J >= H)
        {
        j = (J % H) * 2;
        }
    else
        {
        j = (J * 2) + 1;
        }
    j = Calculer(j, H, K-1);
    }
return j;
}
 
void Melanger3(int N, int K)
{
//Allocation mémoire pour le tableau
int *T = new int[N];
 
//boucle
for(int j = 0; j < N; j++)
    {
    T[Calculer(j, N/2, K)] = j+1;
    }
 
//Pour faire écho du résultat
AnsiString R = "";
for(int j = 0; j < N; j++)
    {
    R = R + IntToStr(T[j]) + " ";
    }
Form1->Memo1->Lines->Add(R);
 
//Suppression du tableau
delete [] T;
}

En attendant le soleil...

A plus !

05/07/2007, 14h25
acx01b

zut il y a des endroits où j'ai mis %(n+1) c'était évidement %(N+1) qu'il fallait mettre

LA SOLUTION

avec le même problème que l'énnoncé (in-shuffle)
(la carte du dessus se retrouve en 2ième place)

les cartes numérotées de 0 à N-1

on a pour N pair:
si k < N/2 : k -> 2k + 1
si k >= N/2 : k -> 2(k-N/2)
on a donc k -> 2k + 1 % (N+1)

ce qui donne comme solution plus petit n tel que N+1 divise 2^n-1

avec l'autre problème (out-shuffle)
(la carte du dessus reste au dessus)

les cartes toujours numérotées de 0 à N-1

on a pour N pair:
si k < N/2 : k -> 2k
si k >= N/2 : k -> 2(k-N/2) + 1
on a donc k -> 2k % (N-1)

ce qui donne comme solution plus petit n tel que N-1 divise 2^n-1

ensuite si on appelle la première façon in-shuffle et la deuxième out-shuffle

on a pour N pair:
out-shuffle sur N = in-shuffle sur N-1

donc pour N pair ou impair le in-shuffle est résolu
05/07/2007, 15h11
Zavonen

J'avais posté

Citation:

Donc l'ordre du cycle correspond au plus petit entier k tel que 2^k=1 mod[N-1]

Donc c'est bien la même chose que

Citation:

ce qui donne comme solution plus petit n tel que N-1 divise 2^n-1

Le seul problème est que je ne satisfais pas de cette 'solution' qui oblige à faire une recherche par tests. Je recherche une fonction me permettant de remplir le tableau directement.

Voir 40 message(s) de cette discussion en une page