Passer par toutes les permutations d'un ensemble récursivement

Je suis en train d'écrire une fonction récursive pour produire toutes les permutations d'un tableau.

static int permus[] = new int[] { 1, 2, 3, 4, 5 };


static void testPermu(int start)
{
    //Print it
    System.out.println(Arrays.toString(permus));

    int k;
    for (int i = start + 1; i < permus.length; i++) {
        //swap
        k = permus[start];
        permus[start] = permus[i];
        permus[i] = k;

        testPermu(i);

        //unswap
        k = permus[start];
        permus[start] = permus[i];
        permus[i] = k;
    }
}

Il est invoqué comme testPermu(0) et devrait produire toutes les permutations, cependant cela ne fonctionne pas. Comment puis-je résoudre ce problème?

Il doit être récursive, chaque fois que la fonction est appelée, elle doit obtenir une nouvelle permutation.

de sortie est maintenant

[1, 2, 3, 4, 5] 
[2, 1, 3, 4, 5] 
[2, 3, 1, 4, 5] 
[2, 3, 4, 1, 5] 
[2, 3, 4, 5, 1] 
[2, 3, 5, 4, 1] 
[2, 4, 3, 1, 5] 
[2, 4, 3, 5, 1] 
[2, 5, 3, 4, 1] 
[3, 2, 1, 4, 5] 
[3, 2, 4, 1, 5] 
[3, 2, 4, 5, 1] 
[3, 2, 5, 4, 1] 
[4, 2, 3, 1, 5] 
[4, 2, 3, 5, 1] 
[5, 2, 3, 4, 1]

Vous pouvez voir que beaucoup de permutations sont manquants.

Je vais écrire en Java, mais je vais comprendre, par exemple en C, javascript ou autre chose tant qu'il ne l'utilise pas certains de la bibliothèque de trucs, non disponible en Java.

Voir ici. Je voudrais essayer de le modèle de mon code par la suite. Je ne suis pas sûr, mais je pense que vos problèmes pourraient être découlant de l'utilisation d'un unique tableau statique.
Je suis tout à fait certain que l'exemple que vous avez lié utilise également le même tableau de partout, c'est passé par référence. Je vais essayer de copier cette approche (qui semble être en grande partie le même que le mien :D)
Dans ce cas, votre question doit être marqué comme un doublon.

OriginalL'auteur MightyPork | 2015-03-01

Voici un exemple complet:

package eric.math;

import java.util.Arrays;

public class Permute {
    //swap 2 elements of an array,
    void swap(int[] arr, int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    /**
     * print permutations of array
     * @param arr
     *            original int array,
     */
    void permute(int[] arr) {
        permute(arr, 0, arr.length - 1);
    }

    /**
     * print permutations of array
     * 
     * @param arr
     *            original int array,
     * @param i
     *            start index
     * @param n
     *            end index
     */
    void permute(int[] arr, int i, int n) {
        int j;
        if (i == n)
            System.out.println(Arrays.toString(arr));
        else {
            for (j = i; j <= n; j++) {
                swap(arr, i, j);
                permute(arr, i + 1, n);
                swap(arr, i, j); //backtrack
            }
        }
    }

    public static void main(String[] args) {
        int arr[] = { 1, 2, 3 };
        new Permute().permute(arr);
    }
}

OriginalL'auteur Eric Wang

4

Trois corrections sont nécessaires afin de travailler:
- impression que si (start == permus.length-1), sinon, vous allez voir des doublons
- démarrer le for boucle de i = start, pas i = start + 1
- de manière récursive appel testPermu(start + 1); au lieu de testPermu(i);
OriginalL'auteur Miljen Mikic

@Enric solution est gentil, mais en utilisant une solution ci-dessous, nous pouvons éviter de 80 swaps et d'effectuer seulement 24 swaps.

static void permutation(int[] a, int i, int j) {
    for (; j < a.length && i < a.length; j++) {
        int[] temp = null;
        if (i != j) {
            temp =  swap(a, i, j);
            System.out.println(Arrays.toString(temp));
        }else{
            temp = a;
        }
        permutation(temp, i + 1, i + 1);
    }
}

public static void main(String[] args) {
    int[] a = { 0, 1, 2, 3 };
    permutation(a, 0, 0);
}

OriginalL'auteur Ankush G

Une autre approche:

static ArrayList<ArrayList<Integer>> getPermutation(ArrayList<Integer> ints) {
    if (ints.size() == 1) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        list.add(ints);
        return list;
    } else {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for (Integer i: ints) {
            ArrayList<Integer> subList = new ArrayList<>(ints);
            subList.remove(i);
            ArrayList<ArrayList<Integer>> subListNew = getPermutation(subList);
            for (ArrayList<Integer> _list: subListNew) {
                ArrayList<Integer> local = new ArrayList<>();
                local.add(i);
                local.addAll(_list);
                list.add(local);
            }
        }
        return list;
    }
}

Cette méthode sélectionne d'abord un élément, l'enlève et obtient une sous-liste, puis produit une permutation de la sous-liste jusqu'à ce que la taille de la liste devient 1.

Le principe sous-jacent est en fait de même, mais à l'aide de ArrayList est beaucoup plus pratique. Vous pouvez aussi regarder Système.arraycopy si vous souhaitez mettre en œuvre la méthode dans le tableau simple, ou de faire la conversion à l'aide de Tableaux.asList() et de la liste de la méthode toArray()

OriginalL'auteur tonychow0929

0

Essayer avec
```
testPermu(start + 1);
```
OriginalL'auteur Luka Rahne

J'aime @tony200910041 approche, mais peut-être que quelqu'un désire une plus propre et plus générique version:

public static <T> List<List<T>> getPermutations(List<T> list) {
  if (list.size() == 1)
    return Collections.singletonList(list);

  List<List<T>> perms = new ArrayList<>();
  for (T element: list) {
    List<T> subList = new ArrayList<>(list);
    subList.remove(element);
    List<List<T>> subPerms = getPermutations(subList);
    for (List<T> subPerm: subPerms) {
      List<T> perm = new ArrayList<>();
      perm.add(element);
      perm.addAll(subPerm);
      perms.add(perm);
    }
  }
  return perms;
}

Le tri de la liste avant de passer à l' getPermutations() fonction si vous voulez que votre permutations dans l'ordre croissant.

OriginalL'auteur Oneiros

-1

Vous pouvez le faire simplement sans récursivité

public static Integer[] permutate(int i)
{
    int length = permus.length;
    Integer[] result = new Integer[length];

    List<Integer> chosen = new ArrayList<Integer>(Arrays.asList(permus));

    int divider = 1;
    for (int j=2; j<length; j++)
    {
        divider *= j;
    }

    for (int j=length; j>1; j--)
    {
        int index = i/divider;
        result[length - j] = chosen.remove(index);
        i = i - divider * (i/divider);
        divider = divider / (j-1);
    }
    result[length -1] = chosen.remove(0);

    return result;      
}

OriginalL'auteur Darren

-2

Comment au sujet de la suite de l'algorithme (en pseudo-code)
```
iterate over elements:
   pick one of the element at random 
   call function again on the remaining elements
   if elements.size == 1 
       return or print
```
Cela doit produire un valide permutation à chaque exécution. Si vous voulez que toutes les permutations possibles, tout s'accumulent à mesure que vous parcourez, alors vous devriez avoir toutes les permutations.

OriginalL'auteur posdef

Vous devez vous connecter pour publier un commentaire.