Question

J'ai besoin d'un algorithme capable de mapper les exécutions d'une permutation sur un nombre unique, mais aussi de réduire les nombres suivants.

Ainsi, une exécution est un ensemble séquentiel de nombres dans une permutation qui est triée et en ordre. Dans la liste, 1; 2; 3; 5; 6; 4, il y a deux points, 1; 2; 3 et 5; 6. Je souhaite les remplacer par un nombre unique, un minimum. Ainsi, si, après suppression des analyses, nous avons une permutation de 4 éléments, cette permutation utilise les nombres 1 ... 4. Dans ce qui précède, nous devons réduire les deux analyses. . le premier passage serait 1, 4 se transforme en 2 et [5; 6] se transforme en 3, pour tenir le deuxième critère. Si je trie la permutation réduite, puis développe les éléments de la cartographie et trie la permutation initiale, le résultat sera le même. La permutation résultante ne devrait pas contenir d’essais.

Par exemple (j'ai mis en évidence les pistes): 

(1;2;3;4;5;6) => 1 //Mappings: 1->1;2;3;4;5;6
(2;3;4);1;(5;6) => 2 1 3 // Mappings: 2->2;3;4, and 3->5;6
(3;4);(1;2);(5;6) => 2 1 3 // Mappings: 2->3;4, and 1->1;2 and 3->5;6

pour l'instant, je passe la liste et fais une liste de listes, regroupant les pistes. Vraiment, la deuxième partie est la partie la plus difficile à résoudre. J'ai pensé à l'approche naïve, curieux de savoir si quelqu'un a quelque astuce qui peut le faire mieux que le mien, je suis comme O (2n + n log n),

  • remplacer les analyses par l'élément head de l'analyse et insérer ces données dans une table de hachage (pour la possibilité de récupération)
  • trier pour créer une carte avec les chiffres manquants avec son index trié. [1; 6; 5; 4] produirait [(1,1); (4,2); (5,3); (6,4)]
  • remplacez la liste de l'étape 1 par la carte créée à l'étape 2 et mettez à jour la table de hachage pour la traduction.

parcourant un exemple, encore une fois: 

step 1: replace runs with the head element of the run and inserting data into a hash table  
    [1;3;4;2;5;6;] -> [1;3;2;5]  
step 2: sort array to create map  
    [1235], so we know that, in the previous array, 1 maps to 1, 2 to 2, 3 to 3, 4 to 5.  
step 3: do above translation on array from step one. 
    [1;3;2;4]

Si je trie cette permutation et reconstruis: [1; 2; 3; 4], 3 - > 3; 4 et 4 - > 5; 6 je reçois, 1; 2; 3 ; 4; 5; 6. Egalement trié.

J'utilise des listes, une approche fonctionnelle serait donc préférable. Aucun code nécessaire. Bien sûr, toutes les idées sont les bienvenues.

EDIT:

  

mweerden:

     
    

Les conditions précises sur la cartographie ne sont pas claires pour moi. Pourquoi n'est-il pas autorisé à produire simplement la permutation [1,2, ..., N] pour une permutation avec N pistes? Vous semblez préférer associer une course à un nombre de cette course, mais (comme ce n'est pas toujours possible), vous semblez permettre une certaine liberté. & # 8211;

  

Je ne préfère pas mapper une série sur un numéro de cette série (voir ci-dessus!), mais je dois conserver un ordre . La permutation [1; 2; 3 ... N] est une course et peut donc être réduite davantage. C'est pourquoi il est invalide. L'ordre interviendra dans les opérations ultérieures d'un autre algorithme, mais les éléments individuels peuvent être étendus à la fin pour sauver la permutation initiale.

Était-ce utile?

La solution

Notation:

  • le décompte commence à 1
  • l.i est l'élément i de la liste l
  • l+m est la concaténation des listes m et [n,n+1,n+2,...,m]
  • une exécution est une sous-liste maximale représentant une liste n pour certains n <= m et p avec [1,2,...,N]

On nous donne donc une permutation r_1,r_2,...,r_M de la liste p = r_1+r_2+...+r_M. Nous divisons q en pistes [1,2,...,M] telles que r_(q.1)+r_(q.2)+...+r_(q.M) = [1,2,...,N]. Nous cherchons alors une permutation p = [1,3,4,2,5,6] de N=6 telle que M=4.

Par exemple, si r_1 = [1], nous avons r_2 = [3,4], r_3 = [2], r_4 = [5,6], [1,3,2,4], r_1+r_3+r_2+r_4 = [1]+[2]+[3,4]+[5,6] = [1,2,3,4,5,6], i < M et q.i + 1 = q.(i+1). Dans ce cas, nous devons r_(q.i)+r_(q.(i+1)) = r_(q.i)+r_(q.i + 1) être r_(q.i)+r_(q.i + 1) comme r_(q.i).

Notez que r_(q.i + 1) ne peut pas contenir de longueur supérieure à un par définition; Si tel est le cas, il existe alors un O(1) avec runheads = [r_1.1,r_2.1,...,r_M.1] et donc une sous-liste N de heads, mais runheads est également une sous-liste de O(n) qui contredit que r_i et r_i.1 sont fonctionne.

Désormais, pour trouver un 1 <<>, nous supposons la disponibilité d'une structure de données de mappage avec k des insertions et des recherches de numéros et de listes avec i -> k des ajouts et un parcours en avant. Ensuite, nous procédons comme suit.

  • Tout d'abord, nous construisons la liste f. Cela peut être fait de manière triviale en parcourant rev tout en maintenant l'exécution actuelle. Au cours de cette étape, nous nous souvenons également du nombre maximal rencontré pour obtenir k -> i à la fin et construire un mappage k -> runheads(i) avec les éléments de runheads = [1,3,2,5] en tant que clés. Cette étape est clairement heads = { 1 -> [1], 3 -> [3,4], 2 -> [2], 5 -> [5,6] }. Notez que les valeurs de 2 ne sont pas pertinentes, nous pouvons donc utiliser run 3 comme valeur pour la clé 5.

  • Ensuite, nous passons de 4 à (et inclus) { 1 -> 1, 2 -> 2, 3 -> 3, 5 -> 4 } en maintenant une valeur { 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 5 } avec une valeur initiale { 1 -> [1], 2 -> [2], 3 -> [3,4], 4 -> [5,6] }. Pour chaque valeur map(f,runheads), nous vérifions si [f(1),f(3),f(2),f(5)] est dans O(n*log(n)). Si tel est le cas, nous ajoutons <=> à un mappage <=> et augmentons <=>. Cette étape est également clairement <=>. Pour pouvoir revenir de <=> à <=>, nous pouvons également stocker un mappage supplémentaire <=> avec <=> ou même <=> sans aucun coût supplémentaire.

  • Enfin, nous appliquons la cartographie <=> aux éléments de <=> pour obtenir <=>. Encore une fois <=>.

Pour illustrer avec un exemple, examinons le cas où <=>.

  • Dans la première étape, nous obtenons <=>, <=> et <=>.

  • Pour la deuxième étape, nous avons quatre cas pour lesquels nous devons faire quelque chose: <=>, <=>, <=> et <=>. Pour ces cas, nous avons des valeurs pour <=> qui sont respectivement <=>, <=>, <=> et <=>. Cela signifie que <=> sera <=>. (Et <=> serait <=> ou <=>, selon ce que vous avez choisi de stocker.)

  • Pour obtenir <=> nous calculons <=> qui est <=> ou, de manière équivalente, <=>.

Donc, si je ne fais pas d'erreur et si les structures de données répondent aux exigences ci-dessus, cette solution devrait être <=>. Notez qu'en pratique, il pourrait être plus utile d'utiliser votre propre solution (<=>). Si vous avez un grand <=> mais avec juste quelques essais, trier <=> et l'utiliser pour créer les mappages peut s'avérer plus efficace. Je pense que <=> devrait être assez gros pour que ce soit le cas.

Autres conseils

Modifié pour clarification

étape 1: Exécutez l'algorithme mais au lieu de produire une seule table de hachage, produisez une table de hachage (D1) indexée par l'en-tête de l'ensemble vers lequel elle est mappée (par exemple, pour [3,4] qui sera 3) et une liste (L1) avec l'ensemble lui-même

[3; 4; 6; 8; 1; 2]: 

   D1              L1

3 -> [3,4]     1 -> [3,4]

6 -> [6]       2 -> [6]

8 -> [8]       3 -> [8]

1 -> [1,2]     4 -> [1,2]

Étape 2: Si vous regardez les collections que vous avez maintenant, vous verrez que, pour un ensemble donné, nous avons l’index dans lequel nous l’avons trouvé (en L1) et la valeur Head. La valeur de carte correcte sera le nombre entier minimum entre eux qui n'est pas déjà pris. Par exemple, pour le [3,4] nous aurons que la valeur doit être comprise entre 1 et 3, et, puisque 1 est déjà pris, la valeur correspondante est 2. Prenez en compte que, comme D1 est indexé par le Head valeur, les valeurs les plus basses seront toujours prises si le jeu correspondant existe. Dans l'exemple, [1,2] est mappé sur 1, de sorte que cette clé est déjà & "Prise &"; Donc, en pseudocode: 

for (int Current = 1; Current  < L1.Length; Current++)
{
  GetHead(L1[Current]);
  Index = Current;
  While Head > Index
  {
    if D1.Empty(Index)
    {
      D1.Add(Index,D2[Current])
      D1.DeleteIfNotEmpty(Head);
    }
    else
      Index++;
  }
}

Par exemple

  • nous prenons la première valeur dans L1 - > [3,4] ...
  • obtenir la tête = 3
  • À partir de 1, nous cherchons D1 [1] qui est déjà pris, nous incrémentons donc à 2.
  • Nous cherchons D1 [2] qui est vide, donc nous assignons D1 [2] = [3,4] et supprimons D [3]

Cela ne fournit pas O (n) mais quelque chose comme O (n + log (n)) (n pour la première étape, log (n) pour la seconde)

Pour l'exemple ci-dessus, vous obtenez: 

1 -> [1,2]
2 -> [3,4]
3 -> [6]
4 -> [8]

Maintenant, si vous avez [3; 4; 8; 6; 1; 2], cela entraînera 

1 -> [1,2]
2 -> [3,4]
3 -> [8]
4 -> [6]

parce qu'il utilise un ordre absolu dans le tableau d'origine, je ne sais pas si cela vous convient ou si vous voulez que 6 soit dans l'index 3 et 8 dans l'index 4, dans ce cas vous aurez probablement pour pré-commander L1 en fonction de la tête, ce qui augmentera votre complexité par Log (n)

Si vous devez pré-commander, vous aurez 0 (n + log ^ 2 (n)), ce qui n’est pas si grave (peut-être moins si un QuickSort a O (Log n) si vous commandez L1 sera O (log (log n))

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top