我正在尝试递归地生成列表中的所有项目。我已经看到了一些与此类似的问题的解决方案，但我无法让我的代码正常工作。有人可以指出我如何修复我的代码吗？
这对所有 S/O 人员开放，而不仅仅是 Java 人员。
（另外我应该注意到它会因异常而崩溃）。
输入示例：
[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);
}
}
如果
allPossibleItemsDESIRED_SIZEDESIRED_SIZE我会做的（如果原件没有双联/重复）是：
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;
}
输入列表，可能包含重复项。
List<String> list = Arrays.asList("𝟭", "𝟮", "𝟯");
map1: [{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 中使用递归的字符串排列
问题是你必须在进行递归调用之前克隆 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);
}
}
}
谷歌搜索让我想到了这个问题。我发现下面的方法比其他方法更快。
基本上我使用集合来递归生成排列。为了说明，第一个位置可以保存所有可能的值，第二个位置可以保存除第一个值之外的所有可能的值，依此类推。当我们到达最后一个位置时，只有一种可能。
就递归函数的参数而言，（1）我们将已经记录的内容作为当前字符串传递下去。 (2) 我们传递保存结果的 Arraylist - list_of_permutes (3) 我们传递从中选择当前数字的集合 - currentnums。 在最后一级，我们有一个完整的排列，然后将其添加到数组列表 - 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;
}
我研究了这个帖子并分析了正确的解决方案。不幸的是，我需要这种递归来进行大量输入，这将导致创建很多不需要存储的对象，我想对每个排列应用一种方法，并只保留那些满足我的算法的对象，所以我想出了这个解决方案。希望对其他人有帮助。
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);
您可以保持起始位置固定，然后继续交换。这是最容易理解的方法之一。
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));
}
}
Apache Commons Collections 实际上提供了
PermutationIterator4.0public static void main(String[] args) {
// Input list
List<String> list = Arrays.asList("𝟭", "𝟮", "𝟯");
// Use the PermutationIterator
PermutationIterator<String> permutations = new PermutationIterator<>(list);
while (permutations.hasNext()) {
System.out.println(permutations.next());
}
}
这是我对这个排列挑战的解决方案，我使用 DFS 算法构建排列树，我根据所需子集的大小对其进行修剪。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
/**
* Permuation Application
* This class works out all permutations of a given set of elements
*
* @author arshadmayet
*
*/
public class Permutation {
public static final String EMPTY_STRING = "";
/**
* DFS Algorithm to find all permutaions on a sequence of elements
*
* @param pref path of current element in permutation tree
* @param result to store permutations
* @param sequence list of elements to permutate
* @param subset subset size, use size of sequence for the
* entire size per permutation.
* @return all permutations of the given sequence as a String List
*/
public List<String> permutate(String pref, List<String> result,
List<String> sequence, int subset) {
/*
* Get just the unvisited children for tree element
*/
List<String> diff = sequence.stream().filter(x -> !
(pref).contains(x)).collect(Collectors.toList());
/*
* No more children therefore reached end of branch store branch paths
*/
int limit = sequence.size() - subset;
if(diff.size()==limit){
result.add(pref);
}
/*
* Loop thru each child
*/
for (String s : diff) {
if(pref.length()>subset) break; // to trim permuatation tree based on
// result sequence limit
permutate(pref + s, result,sequence,subset); // recursively traverse
//tree
}
return result;
}
public static void main(String[] args) {
Permutation permutation = new Permutation();
// Test 1
String[] sequenceArray1 = { "1", "2", "3" };
List<String> sequence1 = Arrays.asList(sequenceArray1);
int subset1= sequence1.size(); //subset
List<String> results1 = permutation.permutate(EMPTY_STRING,
new ArrayList<String>(),
sequence1,
subset1);
//Display Logic
System.out.println("Test 1");
System.out.println("Sequence "+sequence1);
System.out.println("Subset "+subset1);
System.out.println(results1);
System.out.println("results size = " + results1.size());
System.out.println();
//Test 2
String[] sequenceArray2 = {"1","2","3","4"};
List<String> sequence2 = Arrays.asList(sequenceArray2);
int subset2= 2; //subset
List<String> results2 = permutation.permutate(EMPTY_STRING,
new ArrayList<String>(),
sequence2,
subset2);
//Display Logic
System.out.println("Test 2");
System.out.println("Sequence "+sequence2);
System.out.println("Subset "+subset2);
System.out.println(results2);
System.out.println("results size = " + results2.size());
}
}
输出：
测试 1
序列 [1, 2, 3]
子集 3
[123]
[132]
[213]
[231]
[312]
[321]
结果大小 = 6
测试 2
序列 [1, 2, 3, 4]
子集 2
[12]
[13]
[14]
[21]
[23]
[24]
[31]
[32]
[34]
[41]
[42]
[43]
结果大小 = 12