16

我正在尝试递归地生成列表中的所有项目。我已经看到了一些类似问题的解决方案，但我无法让我的代码正常工作。有人能指出我如何修复我的代码吗？

这对所有 S/O'ers 开放，而不仅仅是 Java 人员。

（另外我应该注意它会因 SO 异常而崩溃）。

样本输入：

[1, 2, 3]

输出：

[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);
    }
}
4

6 回答 6

24

如果allPossibleItems包含两个不同的元素 x 和 y，那么您连续将 x 和 y 写入列表，直到到达DESIRED_SIZE. 那是你真正想要的吗？如果你选择DESIRED_SIZE的足够大，堆栈上的递归调用就会太多，因此会出现 SO 异常。

我会做的是（如果原件没有连拍/重复）是：

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;
}
于 2012-04-24T20:19:42.467 回答
2

问题是您必须在进行递归调用之前克隆ArrayList。否则，您将始终添加到同一个 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);
        }
    }
}
于 2012-04-24T20:11:08.807 回答
1

谷歌搜索导致我这个问题。我发现以下方法比其他方法更快。

基本上我使用 Set 递归地生成排列。为了说明，第一个位置可以保存所有可能的值，第二个位置可以保存除第一个值之外的所有可能值，依此类推。当我们到达最后一个位置时，只有一种可能性。

就递归函数的参数而言，(1) 我们将已经记录的内容作为 currentstring 传递下去。(2) 我们传递保存结果的 Arraylist - list_of_permutes (3) 我们传递从中选择当前数字的集合 - currentnums。在最后一级，我们有一个完整的排列，然后将其添加到 arraylist - list_of_permutes 并向上返回。

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;
}

这可以从以下内容中调用：

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;
}
于 2018-04-03T20:54:54.570 回答
1

map 和reduce方法

  • 输入列表可能包含重复项。

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

  • 该map方法将列表的每个元素表示为排列映射列表。

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

  • 该方法将这些列表对顺序求和，并将映射对连接成一个排列映射reduce的单个列表。

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

在线尝试！

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());
}

另请参阅：Java 中使用递归的字符串排列

于 2021-07-25T03:34:05.003 回答
0

您可以保持开始固定，然后继续交换。这是最容易理解的方法之一。

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));
    }
}
于 2019-05-29T05:44:03.647 回答
0

我查看了这个线程，并分析了正确的解决方案。不幸的是，我需要这个递归来处理大量输入，这将导致创建很多我不需要存储的对象，我想对每个排列应用一个方法并只保留那些满足我的算法的对象，所以我想出了这个解决方案。希望它会帮助别人。

public static <E> void iteratePermutations(List<E> original, Consumer<List<E>> consumer) {
    Objects.requireNonNull(original);
    consumer.accept(original);
    iteratePermutationsRecursively(original, 0, consumer);
}

public static <E> void iteratePermutationsRecursively(List<E> original, int start, Consumer<List<E>> consumer) {
    Objects.requireNonNull(original);
    for (int i = start; i < original.size() - 1; i++) {
        for (int j = i + 1; j < original.size(); j++) {
            List<E> temp = new ArrayList<>(original);
            E tempVal = temp.get(i);
            temp.set(i, temp.get(j));
            temp.set(j, tempVal);
            consumer.accept(temp);
            iteratePermutationsRecursively(temp, i + 1, consumer);
        }
    }
}

我可以被称为：

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
List<List<Integer>> result = new ArrayList<>();
iteratePermutations(list, result::add);

或者：

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
iteratePermutations(list, System.out::println);
于 2020-12-05T10:25:54.020 回答