Problème intéressant sur le tri

14

Étant donné un tube avec des boules numérotées (aléatoire). Le tube a des trous pour retirer une balle. Considérez les étapes suivantes pour une opération:

  1. Vous pouvez choisir une ou plusieurs balles dans les trous et vous souvenir de l'ordre dans lequel vous avez choisi les balles.
  2. Vous devez incliner le tuyau vers le côté gauche afin que les billes restantes dans le tuyau se déplacent vers la gauche et occuper l'espace vide créé en retirant les billes.
  3. Vous n'êtes pas censé changer l'ordre dans lequel vous avez choisi les boules numérotées du tuyau. Maintenant, vous les remettez dans le tuyau en utilisant l'espace libre créé par le mouvement des balles.

Les étapes 1 à 3 sont considérées comme une seule opération.

Découvrez les opérations minimales requises pour trier les boules numérotées dans l'ordre croissant.

Par exemple: Si le tube contient: [1 4 2 3 5 6]

Ensuite, nous pouvons retirer et 5 et 6 , et si nous inclinons le tuyau vers la gauche, nous obtenons [ 1 2 3 ] , et nous insérons ( 4 5 6 ) dans cet ordre à la fin du tuyau pour obtenir [ 1 2 3 4 5 6 ] .456[1 2 3](4 5 6)[1 2 3 4 5 6]

Donc, le nombre minimum d'étapes requises est 1. J'ai besoin de trouver des opérations minimales pour trier le tuyau.

Des idées ou des conseils sur la façon de résoudre ce problème?

rakesh
la source
S'ils viennent dans l'ordre inverse, vous devez retirer 2, 3, ... dans l'ordre et les ajouter à la fin, pour opérations en tout. C'est clairement le pire des cas. n
vonbrand
2
8,7,6,5,4,3,2,1 -> 75318642 -> 51627384 -> 12345678 en prenant toujours des positions impaires.
adrianN
Résumant ma réponse: le nombre minimum d'opérations nécessaires pour trier une permutation est log 2 ( d ( π - 1 ) + 1 ) , où d ( ) est le nombre de descentes. πlog2(d(π1)+1)d()
Yuval Filmus
J'aime y penser en termes de suppression des inversions. Avec chaque opération, vous pouvez supprimer les inversions entre n'importe quel ensemble et S - X (où S est l'ensemble des boules). Donc, il vous suffit de choisir des ensembles X avec soin. XSXSX
Joe

Réponses:

10

Définissez le numéro d' exécution-partition d'une permutation , notée r ( π ) , en utilisant le processus suivant. Soit k l'entier maximal tel que les nombres min ( π ) , , k apparaissent en ordre croissant dans π . Supprimez-les de et répétez le processus. Le nombre de tours qu'il faut pour consommer la permutation entière estπr(π)kmin(π),,kπr ( π )πr(π) .

Par exemple, calculons . Nous avons d'abord mis de côté , pour obtenir . Ensuite, nous avons mis de côté , pour obtenir . Ensuite, nous avons mis de côté , pour obtenir . Enfin, nous avons mis de côté pour obtenir la permutation vide. Cela prend quatre tours, donc1 6273584 234 6758 5 678 678 r ( 62735814 ) = 4r(62735814)1627358423467585678678r(62735814)=4 .

En quoi cette représentation est-elle utile pour trier ? Effectuez toutes les secondes, soit , et déplacez ces nombres vers la droite pour obtenir (modifier: dans l'ordre où ils apparaissent dans la permutation, soit ). Maintenant, il n'y a que deux exécutions, à savoir , et nous pouvons trier la liste en déplaçant vers la droite.234 , 678 51627384 627384 1234 , 5678 567862735814234,678516273846273841234,56785678

Permettez-moi maintenant de faire la conjecture suivante: Pour une permutation , soit l'ensemble de toutes les permutations qui sont accessibles à partir de en un seul mouvement. Alors .Π π min α Π r ( α ) = r ( π ) / 2 πΠπminαΠr(α)=r(π)/2

Compte tenu de cette conjecture, il est facile de montrer que le nombre minimal de mouvements nécessaires pour trier une permutation est , et j'ai vérifié cette formule pour toutes les permutations dans pour .log 2 r ( π ) S n n 8πlog2r(π)Snn8

Edit: Voici une interprétation différente du numéro de la partition d'exécution qui donne un algorithme de temps linéaire pour le calculer, et me permet d'esquisser une preuve de ma conjecture, vérifiant ainsi la formule .log2r(π)

Considérez à nouveau la permutation . La raison pour laquelle la première exécution se termine par est que apparaît avant . De même, la deuxième manche se termine en puisque apparaît avant , et ainsi de suite. Par conséquent, le numéro de partition d'exécution d'une permutation est le nombre de s tel que apparaisse avant .1 2 1 4 5 4 i i + 1 i62735814121454ii+1i

Nous pouvons le dire plus succinctement si nous regardons l'inverse de la permutation. Considérez à nouveau . Prenez . Cette permutation a trois descentes: (une descente est une position plus petite que la précédente). Chacune des descentes correspond au début d'une nouvelle descente. Donc est égal à un plus le nombre de descentes dansπ - 1 = 72485136 7 2 48 5 1 36 r ( π ) π - 1π=62735814π1=7248513672485136r(π)π1 .

À quoi ressemble l'opération en termes de ? soit l'ensemble des nombres que nous déplaçons vers la droite, et l'ensemble des nombres qui restent à gauche. Nous remplaçons les nombres dans par une permutation sur représentant leur ordre relatif, et remplaçons les nombres dans par une permutation sur . Par exemple, considérons le mouvement . En termes de permutations inverses, c'est . Donc, correspondait à B A A { 1 , , | A | } B { | A | + 1 , , | A | + | B | } 6273 5 8 1 451 627384 7 248 5 1362 468 1 357 75 21 248 136 468 357π1BAA{1,,|A|}B{|A|+1,,|A|+|B|}627358145162738472485136246813577521 et248136a été mappé sur468357 .

Une descente dans π - 1 est perdu après l'opération que si x A et y B . Inversement, en termes de π - 1 , la partition en A et B correspond aux A- run et B- run; chaque fois qu'une course B se termine et qu'une course A commence, il y a une descente. Pour "tuer" une descente, nous devons passer d'un A- run à un Bxyπ1xAyBπ1ABABBAAB-courir. Si nous tuons deux descentes, nous serons passés au milieu d'un run à un ABA run, entraînant une descente.

Cet argument peut être formalisé pour montrer que si provient de via une opération, alors , où est le nombre de descentes. Cela équivaut à , prouvant ainsi une direction de ma conjecture. L'autre direction est plus facile, et a déjà été décrite ci-dessus: nous prenons simplement chaque seconde course et poussons ces courses vers la droite pour obtenir une permutation satisfaisant r ( α ) = r ( π / 2 ) απd(α1)d(π1)/2d()r(α)r(π)/2αr(α)=r(π/2) .

Yuval Filmus
la source
Vous sortez plusieurs tours de balles à la fois, je comprends que ce n'est pas autorisé.
vonbrand
1
Je les prends dans l'ordre où ils apparaissent dans la permutation . C'est légal.
Yuval Filmus
je suis un peu confus. pouvez-vous s'il vous plaît expliquer le nombre minimum d'opérations nécessaires pour trier [6 5 4 3 2 1] et vous avez également mentionné comme "Prenez chaque deuxième série, soit 234 678, et déplacez ces chiffres vers la droite pour obtenir 51627384" pouvez-vous s'il vous plaît expliquer cela avec détail et aussi comment calculer r (π) efficacement?
user6709
1) , vous auriez donc besoin de 3 opérations. Par exemple, 654321 531 | 642 51 | 6234 1234 | 56 . r(654321)=6654321531|64251|62341234|56
Yuval Filmus
2) Vous prenez tous les nombres appartenant à ces pistes (dans l'ordre où ils apparaissent dans la permutation), et vous les déplacez vers la droite. Dans ce cas, vous prenez et les déplacez vers la droite, en laissant 51 vers la gauche. 62738451
Yuval Filmus