Génération récursive de toutes les permutations possibles d'une liste

Question

J'essaie de générer récursivement tous les éléments d'une liste. J'ai vu quelques solutions à des questions similaires à celle-ci, mais je n'ai pas réussi à faire fonctionner mon code. Quelqu'un pourrait-il m'indiquer comment corriger mon code ?

C'est ouvert à tous les S/O'ers, pas seulement aux Java.

(Je dois également noter qu'il se bloque avec une exception SO).

Entrée de l'échantillon :

[1, 2, 3]

Sortie :

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

//allPossibleItems is an AL of all items 

//this is called with generatePerm(null, new ArrayList<Item>);

private void generatePerm(Item i, ArrayList<Item> a) {
    if (i != null) { a.add(i); }
    if (a.size() == DESIRED_SIZE) {
        permutations.add(a);
        return;
    }
    for (int j = 0; j < allPossibleItems.size(); j++) {
        if (allPossibleItems.get(j) != i)
            generatePerm(allPossibleItems.get(j), a);
    }
}

Answer 1

Si allPossibleItems contient deux éléments différents, x et y, alors vous écrivez successivement x et y dans la liste jusqu'à ce qu'elle atteigne DESIRED_SIZE . Est-ce que c'est ce que vous voulez vraiment ? Si vous choisissez DESIRED_SIZE suffisamment grande, vous aurez trop d'appels récursifs sur la pile, d'où l'exception SO.

Ce que je ferais (si l'original n'a pas de doublets / duplicatas) est :

public <E> List<List<E>> generatePerm(List<E> original) {
  if (original.isEmpty()) {
    List<List<E>> result = new ArrayList<>();
    result.add(new ArrayList<>());
    return result;
  }
  E firstElement = original.remove(0);
  List<List<E>> returnValue = new ArrayList<>();
  List<List<E>> permutations = generatePerm(original);
  for (List<E> smallerPermutated : permutations) {
    for (int index = 0; index <= smallerPermutated.size(); index++) {
      List<E> temp = new ArrayList<>(smallerPermutated);
      temp.add(index, firstElement);
      returnValue.add(temp);
    }
  }
  return returnValue;
}

Answer 2

Le problème est que vous devez clone l'ArrayList avant de faire l'appel récursif. Sinon, vous ajouterez toujours à la même ArrayList.

//allPossibleItems is an AL of all items

//this is called with generatePerm(null, new ArrayList<Item>);

private void generatePerm(Item i, ArrayList<Item> a) {
    if (i != null) { a.add(i); }
    if (a.size() == DESIRED_SIZE) {
        permutations.add(a);
        return;
    }
    for (int j = 0; j < allPossibleItems.size(); j++) {
        if (!a.contains(allPossibleItems.get(j))) {
            ArrayList<Item> b = clone(a);
            generatePerm(allPossibleItems.get(j), b);
        }
    }
}

Answer 3

Une recherche sur Google m'a conduit à cette question. J'ai trouvé la méthode ci-dessous plus rapide que les autres.

En gros, j'utilise un Set pour générer récursivement les permutations. Pour illustrer, la première position peut contenir toutes les valeurs possibles, la deuxième toutes les valeurs possibles sauf la première, et ainsi de suite. Lorsque nous arrivons à la dernière position, il n'y a qu'une seule possibilité.

En termes de paramètres à la fonction récursive, (1) nous transmettons ce qui a déjà été enregistré en tant que currentstring. (2) Nous passons la Arraylist qui contient les résultats - list_of_permutes (3) Nous passons le jeu à partir duquel choisir le nombre actuel - currentnums. Au dernier niveau, nous avons une permutation complète, qui est ensuite ajoutée à la Arraylist - list_of_permutes et celle-ci est retournée vers le haut.

public static ArrayList recurse_nums(Set<Integer> currentnums,
                                     String currentstring,
                                     ArrayList list_of_permutes) {
    if (currentnums.size() == 1) {
        int elem = currentnums.iterator().next();
        list_of_permutes.add(currentstring + Integer.toString(elem));
        return list_of_permutes;
    }
    for (int a : currentnums) {
        String newstring = currentstring + a;
        Set<Integer> newnums = new HashSet<>();
        newnums.addAll(currentnums);
        newnums.remove(a);
        recurse_nums(newnums, newstring, list_of_permutes);
    }
    return list_of_permutes;
}

Ceci peut être appelé à partir de quelque chose comme ce qui suit :

public static ArrayList permute_array(int[] arr) {
    Set<Integer> currentnums = new HashSet<>();
    for (int i = 0; i < arr.length; i++) {
        currentnums.add(arr[i]);
    }
    ArrayList permutations = new ArrayList();
    recurse_nums(currentnums, "", permutations);
    return permutations;
}

Answer 4

El cartographier et réduire approche

• La liste d'entrée, peut contenir des doublons.

  List<String> list = Arrays.asList("", "", "");

• El map représente chaque élément d'une liste comme un liste des cartes de permutation .

  1: [{0=}, {1=}, {2=}]
  2: [{0=}, {1=}, {2=}]
  3: [{0=}, {1=}, {2=}]

• El reduce additionne séquentiellement des paires de ces listes et concatène les paires de cartes en une seule liste des cartes de permutations .

  {0=, 1=, 2=}
  {0=, 2=, 1=}
  {1=, 0=, 2=}
  {1=, 2=, 0=}
  {2=, 0=, 1=}
  {2=, 1=, 0=}

Essayez-le en ligne !

public static void main(String[] args) {
    // input list
    List<String> list = Arrays.asList("", "", "");
    // possible permutations
    List<Map<Integer, String>> pp = possiblePermutations(list);
    // output
    pp.forEach(System.out::println);
}

/**
 * @param list the input list, may contain duplicates
 * @param <E>  the type of the element of the list
 * @return the list of possible permutations
 */
public static <E> List<Map<Integer, E>> possiblePermutations(List<E> list) {
    // check if the list is non-null and non-empty
    if (list == null || list.size() == 0) return Collections.emptyList();
    return IntStream.range(0, list.size())
            // represent each list element as a list of permutation maps
            .mapToObj(i -> IntStream.range(0, list.size())
                    // key - element position, value - element itself
                    .mapToObj(j -> Collections.singletonMap(j, list.get(j)))
                    // Stream<List<Map<Integer,E>>>
                    .collect(Collectors.toList()))
            // reduce a stream of lists to a single list
            .reduce((list1, list2) -> list1.stream()
                    .flatMap(map1 -> list2.stream()
                            // filter out those keys that are already present
                            .filter(map2 -> map2.keySet().stream()
                                    .noneMatch(map1::containsKey))
                            // concatenate entries of two maps, order matters
                            .map(map2 -> new LinkedHashMap<Integer, E>() {{
                                putAll(map1);
                                putAll(map2);
                            }}))
                    // list of combinations
                    .collect(Collectors.toList()))
            // otherwise an empty collection
            .orElse(Collections.emptyList());
}

---

Voir aussi : Permutations de chaînes de caractères à l'aide de la récursion en Java

Answer 5

Vous pouvez garder le départ fixe et ensuite continuer à échanger. C'est l'une des approches les plus faciles à comprendre.

public class PermutationListRecursion {
    private Set<List<Integer>> permList = new HashSet<>();

    public static void main(String[] args) {
        PermutationListRecursion pt = new PermutationListRecursion();
        Integer[] nums = {1, 2, 3};
        pt.permute(nums);
        System.out.println(pt.permList);
    }

    public void permute(Integer[] nums) {
        permutation(0, nums.length - 1, nums);
    }

    public void permutation(int start, int end, Integer[] nums) {
        if (start == end) {
            permList.add(new ArrayList<Integer>(Arrays.asList(nums)));
        }
        for (int i = start; i <= end; i++) {
            permList.add(swap(nums, start, i));
            permutation(start + 1, end, nums);
            permList.add(swap(nums, start, i));
        }
    }

    private List<Integer> swap(Integer[] arr, int a, int b) {
        if (a == b) {
            return new ArrayList<>(Arrays.asList(arr));
        }
        Integer temp = arr[b];
        arr[b] = arr[a];
        arr[a] = temp;
        return new ArrayList<>(Arrays.asList(arr));
    }
}