数组列表中字符串的排列(使用递归)

Question

我一直在努力弄清楚这一点，现在只是不能完全理解我打算如何创建预期的输出。我设法得到输入和唯一排列的最大数量，所有我现在需要的是找出如何获得预期的字符串作为输出。我认为有更好的方法来做这件事。

输入:Julia Lucas Mia -1

预期输出:

Julia, Lucas, Mia

Julia, Mia, Lucas

Lucas, Julia, Mia

Lucas, Mia, Julia

Mia, Julia, Lucas

Mia, Lucas, Julia

import java.util.Scanner;
import java.util.ArrayList;
public class PhotoLineups {
// TODO: Write method to create and output all permutations of the list of names.
public static void printAllPermutations(ArrayList<String> permList, ArrayList<String> nameList){
int size = nameList.size();
int index = 0;
for(int i = size; i > 1; i--)
size = size * (i - 1);
System.out.println("Size: " +size); //Temp
if(index != size){
for(int i = 0; i < nameList.size(); i++){

index++;
}
}
}
public static void main(String[] args){
Scanner scnr = new Scanner(System.in);
ArrayList<String> nameList = new ArrayList<String>();
ArrayList<String> permList = new ArrayList<String>();
String name;
int i = 0;

// TODO: Read in a list of names; stop when -1 is read. Then call recursive method.
while(i != -1){
name = scnr.next();
nameList.add(name);
if(name.equals("-1"))
i = -1;
}
nameList.remove(nameList.size() - 1);
System.out.println("nameList: " + nameList); //Temp
//Recursive
printAllPermutations(permList, nameList);
}
}

Answer 1

在这种情况下递归意味着将问题拆分为一个步骤和其余步骤。所以算法会在循环中选择列表中的名字并将其与其余的排列组合起来。如果剩下的是空的，你得到一个排列:你必须复制List，因为它们是通过引用传递的…

public static void printAllPermutations(ArrayList<String> permList, ArrayList<String> nameList){
if (nameList.isEmpty()) {
System.out.println(String.join(", ", permList));
return;
}
for(int i = 0; i < nameList.size(); i++) {
ArrayList<String> localPermList = new ArrayList<>(permList);
ArrayList<String> localNameList = new ArrayList<>(nameList);
localPermList.add(nameList.get(i));
localNameList.remove(nameList.get(i));
printAllPermutations(localPermList, localNameList);
}
}

编辑

复制了你的代码，你最好把循环写成

for(String name : nameList) {
ArrayList<String> localPermList = new ArrayList<>(permList);
ArrayList<String> localNameList = new ArrayList<>(nameList);
localPermList.add(name);
localNameList.remove(name);
printAllPermutations(localPermList, localNameList);
}