Comment calculer les permutations en temps linéaire, avec une torsion

Question

J'ai un problème de planification des ressources en Java, il faut séquencer les éléments mais il existe des restrictions quant aux ressources pouvant être proches les unes des autres. Une bonne analogie est une chaîne de & "; Chiffres &"; Où seuls certains chiffres peuvent être côte à côte. Ma solution était récursive et fonctionne bien pour les petites chaînes, mais le temps d'exécution est O (X ^ N), où X est le nombre de chiffres possibles (la base) et N la longueur de la chaîne. Cela devient vite ingérable.

En utilisant la matrice de compatibilité ci-dessous, voici quelques exemples de chaînes autorisées.
Longueur de 1: 0, 1, 2, 3, 4
Longueur de 2: 02, 03, 14, 20, 30, 41
Longueur de 3: 020, 030, 141, 202, 203, 302, 303, 414

     0  1  2  3  4
   ---------------------
0|  0  0  1  1  0
1|  0  0  0  0  1
2|  1  0  0  0  0
3|  1  0  0  0  0
4|  0  1  0  0  0

Ma solution pour compter toutes les chaînes de longueur N était de commencer par une chaîne vide, de permuter le premier chiffre et de faire un appel récursif pour toutes les chaînes de longueur N-1. Les appels récursifs vérifient le dernier chiffre ajouté et essaient toutes les permutations pouvant être à côté de ce chiffre. Certaines optimisations ont été effectuées pour que je n'essaie pas de permuter 00, 01, 04 à chaque fois, par exemple - seulement 02, 03, mais les performances sont toujours médiocres, car l'échelle va de la base 5 (l'exemple) à la base 4000.

Avez-vous des idées sur une meilleure façon de compter les permutations autres que d'essayer de les énumérer toutes?

Answer 1

Si vous voulez juste le nombre de chaînes d'une certaine longueur, vous pouvez simplement multiplier la matrice de compatibilité avec elle-même quelques fois et faire la somme de ses valeurs.

  

n = longueur de la chaîne
   A = matrice de compatibilité
   nombre de chaînes possibles = somme de A ^{n -1}

Quelques exemples:

n = 1
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 1 0 |
| 0 0 0 0 1 |
sum: 5

n = 3
| 2 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 1 0 |
| 0 0 1 1 0 |
| 0 0 0 0 1 |
sum: 8

n = 8
| 0 0 8 8 0 |
| 0 0 0 0 1 |
| 8 0 0 0 0 |
| 8 0 0 0 0 |
| 0 1 0 0 0 |
sum: 34

La matrice d'origine (ligne i , colonne j ) peut être considérée comme le nombre de chaînes commençant par le symbole i , et dont le symbole suivant est le symbole j . Vous pouvez également le voir sous forme de nombre de chaînes de longueur 2 , commençant par le symbole i et se terminant par le symbole j .

La multiplication matricielle conserve cet invariant. Ainsi, après exponentiation, A ^{n -1} contiendra le nombre de chaînes commençant par le symbole i , a la longueur n et se termine par le symbole j .

Voir Wikipedia: Exponentiation par la quadrature pour obtenir un algorithme permettant de calculer plus rapidement les puissances de la matrice.

(Merci stefan.ciobaca)

Ce cas spécifique se réduit à la formule:

  

nombre de chaînes possibles = f ( n ) = 4 + & # 931; k = 1 .. n 2 ^{& # 8970; k -1 & # 8260; ₂ & # 8971;} = f ( n -1) + 2 ^{& # 8970; n -1 & # 8260; ₂ & # 8971;}

n       f(n)
----    ----
   1       5
   2       6
   3       8
   4      10
   5      14
   6      18
   7      26
   8      34
   9      50
  10      66

Answer 2

Voulez-vous simplement savoir combien de chaînes d'une longueur donnée vous pouvez construire avec les règles de la matrice donnée? Si tel est le cas, une approche comme celle-ci devrait fonctionner:

n = 5
maxlen = 100

combine = [
      [0, 0, 1, 1, 0],
      [0, 0, 0, 0, 1],
      [1, 0, 0, 0, 0],
      [1, 0, 0, 0, 0],
      [0, 1, 0, 0, 0]
   ]

# counts of strings starting with 0,1,...,4, initially for strings of length one:
counts = [1, 1, 1, 1, 1]

for size in range(2, maxlen+1):
   # calculate counts for size from count for (size-1)
   newcount = []
   for next in range(n):
      total = 0
      for head in range(n):
         if combine[next][head]:
            # |next| can be before |head|, so add the counts for |head|
            total += counts[head]
      # append, so that newcount[next] == total
      newcount.append(total)
   counts = newcount
   print "length %i: %i items" % (size, sum(counts))

Answer 3

Votre algorithme semble être optimal.

Comment utilisez-vous ces permutations? Les accumulez-vous dans une liste ou les utilisez-vous un par un? Comme il existe un grand nombre de telles permutations, les performances médiocres sont peut-être dues à une utilisation importante de la mémoire (si vous les collectez toutes) ou à un temps considérable. Vous ne pouvez pas faire des milliards de boucles en un temps trivial.

Répondre au commentaire:

Si vous souhaitez simplement les compter, vous pouvez utiliser la programmation dynamique:

Soit count [n] [m] un tableau, où count [l] [j] est le nombre de permutations dont la longueur est l et se terminant par j,

puis compte [l] [i] = compte [l-1] [i1] + compte [l-1] [i2] + ..., où i1, i2, ... sont les chiffres pouvant précéder i (cela peut être sauvegardé dans un tableau pré-calculé).

Chaque cellule de comptage peut être remplie en additionnant K nombres (K dépend de la matrice compatible). La complexité est donc O (KMN), M est la longueur de la permutation et N le nombre total de chiffres.

Answer 4

Peut-être que je ne comprends pas cela, mais cela ne serait-il pas possible si vous disposiez d'un tableau de listes comportant pour chaque chiffre une liste de chiffres valides pouvant le suivre.

Ensuite, votre routine à générer prendra un résultat accumulé, le numéro du chiffre et le chiffre actuel. Quelque chose comme:

// not really Java - and you probably don't want chars, but you'll fix it
void GenerateDigits(char[] result, int currIndex, char currDigit)
{
    if (currIndex == kMaxIndex) {
        NotifyComplete(result);
        return;
    }
    char[] validFollows = GetValidFollows(currDigit); // table lookup
    foreach (char c in validFollows) {
        result[currIndex] = c;
        GenerateDigits(result, currIndex+1, c);
    }
}

La complexité augmente en fonction du nombre de chiffres à générer, mais cette fonction dépend du nombre total de suivis valides pour un chiffre quelconque. Si le nombre total de suivis est le même pour chaque chiffre, disons k, le temps nécessaire pour générer toutes les permutations possibles sera O (k ^ n), où n est le nombre de chiffres. Désolé, je ne peux pas changer de maths. Le temps nécessaire pour générer n chiffres en base 10 est de 10 ^ n.

Answer 5

Je ne suis pas tout à fait sûr de ce que vous demandez, mais puisqu'il y a potentiellement n! permutations d’une chaîne de n chiffres, vous ne pourrez pas les lister plus rapidement que n !. Je ne sais pas trop comment vous pensez avoir un temps d'exécution de O (n ^ 2).