générer des variations sans répétition / permutations en Java

Utilisation de Dollar C'est simple:

@Test
public void generatePermutations() {
    // digits is the string "0123456789"
    String digits = $('0', '9').join();

    // then generate 10 permutations
    for (int i : $(10)) {
        // shuffle, the cut (0, 4) in order to get a 4-char permutation
        System.out.println($(digits).shuffle().slice(4));
    }
}

Le code pour cela est similaire à celui sans duplicates, avec l'ajout d'une déclaration If-else.check ce Code

Dans le code ci-dessus, éditez la boucle de vue comme suit xxx

travaillé pour moi

Voici mon code Java. N'hésitez pas à demander si vous ne comprenez pas. Le point principal ici est:

1. Triez à nouveau le tableau de caractères. Par exemple: A1 A2 A3 B1 B2 B3 B3 .... (A1 = A2 = A3)
2. générer la permutation et toujours conserver la condition: Index de A1 xxx

Permutation sans répétition est basé sur le théorème, que la quantité de résultats est factorielle du nombre d'éléments (dans ce cas en nombre). Dans votre cas 10! est 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800. La preuve pourquoi il est exactement correct une solution correcte pour la génération également. Bien alors comment. En première position, c'est-à-dire à gauche, vous pouvez avoir 10 chiffres, sur la deuxième position que vous ne pouvez avoir que 9 numéros, car un nombre est sur la position de gauche et nous ne pouvons pas répéter le même nombre, etc. (la preuve est effectuée par induction mathématique ). Alors, comment générer dix premiers résultats? Selon mes connaissances, il est le moyen le plus simple d'utiliser le décalage cyclique. Cela signifie l'ordre du numéro de numéro à gauche sur une position (ou la droite si vous le souhaitez) et le nombre qui déborde de mettre à la place vide. Cela signifie pour les dix premiers résultats:

10 9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1 10
8 7 6 5 4 3 2 1 10 9
7 6 5 4 3 2 1 10 9 8
6 5 4 3 2 1 10 9 8 7
5 4 3 2 1 10 9 8 7 6
... p> BlockQuote>

La première ligne est l'échantillon de base, c'est donc la bonne idée de la mettre en jeu avant la génération. L'avantage est que, à l'étape suivante, vous devrez résoudre le même problème pour éviter les doublons indésirables. P>

dans la prochaine étape ne pivote récursivement que 10-1 numéros 10-1 fois, etc. Cela signifie pour les 9 premiers résultats à l'étape deux: P>

10 9 8 7 6 5 4 3 2 1
10 8 7 6 5 4 3 2 1 9
10 7 6 5 4 3 2 1 9 8
10 6 5 4 3 2 1 9 8 7
10 5 4 3 2 1 9 8 7 6
... p> BlockQuote>

etc, notification, cette première ligne est présente à partir de l'étape précédente, il ne doit donc pas être ajouté à la rédaction générée à nouveau. P>

algorithme faisait de manière récursive exactement cela, ce qui est expliqué ci-dessus. Il est possible de générer toutes les combinaisons 3628800 pour 10!, Car le nombre d'imbruits est identique à celui du nombre d'éléments dans la matrice (cela signifie dans votre cas pendant 10 numéros qu'il persiste environ 5min. Sur mon ordinateur) et vous avez besoin d'avoir assez de mémoire. Si vous souhaitez conserver toutes les combinaisons dans la matrice. P>

Il y a une solution. p>

package permutation;

/** Class for generation amount of combinations (factorial)
 * !!! this is generate proper permutations without repeating and proper amount (počet) of rows !!!
 *
 * @author hariprasad
 */
public class TestForPermutationII {
  private static final String BUMPER = "*";
  private static int counter = 0;
  private static int sumsum = 0;
  // definitoin of array for generation
  //int[] testsimple = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  int[] testsimple = {1, 2, 3, 4, 5};
  private int ELEMNUM = testsimple.length;
  int[][] shuff;

  private String gaps(int len) {
    String addGap = "";
    for(int i=0; i <len; i++)
      addGap += "  ";
    return addGap;
  }

  /** Factorial computing */
  private int fact(int num) {
    if (num > 1) {
      return num * fact(num - 1);
    } else {
      return 1;
    }
  }

  /** Cyclic shift position to the left */  
  private int[] lShiftPos(int[] arr, int pos) {
    int[] work = new int[ELEMNUM];
    int offset = -1;
    for (int jj = 0; jj < arr.length; jj++) {
      if (jj < pos) {
        work[jj] = arr[jj];
      } else if (jj <= arr.length - 1) {
        if (jj == pos) {
          offset = arr[pos]; // last element
        }
        if (jj != (arr.length - 1)) {
          work[jj] = arr[jj + 1];
        } else {
          work[jj] = offset;
        }
      }
    }
    return work;
  }

  private String printBuff(int[] buffer) {
    String res = "";
    for (int i= 0; i < buffer.length; i++) {
      if (i == 0) 
        res += buffer[i];
      else
        res += ", " + buffer[i];
    }
    return res;
  };

  /** Recursive generator for arbitrary length of array */
  private String permutationGenerator(int pos, int level) {
    String ret = BUMPER;
    int templen = counter;
    int[] work = new int[ELEMNUM];
    int locsumread = 0;
    int locsumnew = 0;
    //System.out.println("\nCalled level: " + level);

    for (int i = 0; i <= templen; i++) {
      work = shuff[i];
      sumsum++;
      locsumread++;
      for (int ii = 0; ii < pos; ii++) {
        counter++;
        sumsum++;
        locsumnew++;
        work = lShiftPos(work, level); // deep copy
        shuff[counter] = work;
      }
    }

    System.out.println("locsumread, locsumnew: " + locsumread + ", " + locsumnew);
    // if level == ELEMNUM-2, it means no another shift
    if (level < ELEMNUM-2) {
      ret = permutationGenerator(pos-1, level+1);
      ret = "Level " + level + " end.";
      //System.out.println(ret);
    }
    return ret;
  }

  public static void main(String[] argv) {
    TestForPermutationII test = new TestForPermutationII();
    counter = 0;
    int len = test.testsimple.length;
    int[] work = new int[len];

    test.shuff = new int[test.fact(len)][];

    //initial
    test.shuff[counter] = test.testsimple;
    work = test.testsimple; // shalow copy

    test.shuff = new int[test.fact(len)][];
    counter = 0;
    test.shuff[counter] = test.testsimple;
    test.permutationGenerator(len-1, 0);

    for (int i = 0; i <= counter; i++) {
      System.out.println(test.printBuff(test.shuff[i]));
    }

    System.out.println("Counter, cycles: " + counter + ", " + sumsum);
  }
}

Il y a une solution qui n'est pas du mien, mais c'est très gentil et sophistiqué. XXX

Je pense, c'est l'excellente solution.

J'ai créé le code suivant pour générer des permutations où la commande est importante et sans répétition. Il utilise des génériques pour permuter tout type d'objet:

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Permutations {

    public static <T> Collection<List<T>> generatePermutationsNoRepetition(Set<T> availableNumbers) {
        Collection<List<T>> permutations = new HashSet<>();

        for (T number : availableNumbers) {
            Set<T> numbers = new HashSet<>(availableNumbers);
            numbers.remove(number);

            if (!numbers.isEmpty()) {
                Collection<List<T>> childPermutations = generatePermutationsNoRepetition(numbers);
                for (List<T> childPermutation : childPermutations) {
                    List<T> permutation = new ArrayList<>();
                    permutation.add(number);
                    permutation.addAll(childPermutation);
                    permutations.add(permutation);
                }
            } else {
                List<T> permutation = new ArrayList<>();
                permutation.add(number);
                permutations.add(permutation);
            }
        }

        return permutations;
    }
}

Brève connaissance d'indexation de permutation utile

Créer une méthode qui génère la permutation correcte, étant donné une valeur d'index entre {0 et n! -1} pour "zéro indexé" ou {1 et n!} Pour "un indexé".

Créer une deuxième méthode contenant une "boucle" lorsque la limite inférieure est 1 et la limite supérieure est n !. par exemple .. "Pour (i; i <= n !; i ++)" Pour chaque instance de la boucle, appelez la première méthode, passant I comme argument.

def find(alphabet, alpha_current, str, str_current, max_length, acc):
  
  if (str_current == max_length):
    acc.append(''.join(str))
    return
  
  for i in range(alpha_current, len(alphabet)):
    str[str_current] = alphabet[i]
    
    alphabet[i], alphabet[alpha_current] = alphabet[alpha_current], alphabet[i]
    
    find(alphabet, alpha_current+1, str, str_current+1, max_length, acc)
    
    alphabet[i], alphabet[alpha_current] = alphabet[alpha_current], alphabet[i]
  
  return

max_length = 4
str = [' ' for i in range(max_length)]
acc = list()
find(list('absdef'), 0, str, 0, max_length, acc)

for i in range(len(acc)):
  print(acc[i])

print(len(acc))