我需要 N 个列表中的所有排列,直到程序启动我才知道 N,这是我的 SSCCE(我已经实现了向我建议的算法,但它有一些错误)。
首先,创建 Place 类:
public class Place {
public List<Integer> tokens ;
//constructor
public Place() {
this.tokens = new ArrayList<Integer>();
}
}
然后测试类:
public class TestyParmutace {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
List<Place> places = new ArrayList<Place>();
Place place1 = new Place();
place1.tokens.add(1);
place1.tokens.add(2);
place1.tokens.add(3);
places.add(place1); //add place to the list
Place place2 = new Place();
place2.tokens.add(3);
place2.tokens.add(4);
place2.tokens.add(5);
places.add(place2); //add place to the list
Place place3 = new Place();
place3.tokens.add(6);
place3.tokens.add(7);
place3.tokens.add(8);
places.add(place3); //add place to the list
//so we have
//P1 = {1,2,3}
//P2 = {3,4,5}
//P3 = {6,7,8}
List<Integer> tokens = new ArrayList<Integer>();
Func(places,0,tokens);
}
/**
*
* @param places list of places
* @param index index of current place
* @param tokens list of tokens
* @return true if we passed guard, false if we did not
*/
public static boolean Func( List<Place> places, int index, List<Integer> tokens)
{
if (index >= places.size())
{
// if control reaches here, it means that we've recursed through a particular combination
// ( consisting of exactly 1 token from each place ), and there are no more "places" left
String outputTokens = "";
for (int i = 0; i< tokens.size(); i++) {
outputTokens+= tokens.get(i) +",";
}
System.out.println("Tokens: "+outputTokens);
if (tokens.get(0) == 4 && tokens.get(1) == 5 && tokens.get(2) == 10) {
System.out.println("we passed the guard with 3,5,8");
return true;
}
else {
tokens.remove(tokens.get(tokens.size()-1));
return false;
}
}
Place p = places.get(index);
for (int i = 0; i< p.tokens.size(); i++)
{
tokens.add(p.tokens.get(i));
//System.out.println("Pridali sme token:" + p.tokens.get(i));
if ( Func( places, index+1, tokens ) ) return true;
}
if (tokens.size()>0)
tokens.remove(tokens.get(0));
return false;
}
}
这是此代码的输出:
Tokens: 1,3,6,
Tokens: 1,3,7,
Tokens: 1,3,8,
Tokens: 3,4,6,
Tokens: 3,4,7,
Tokens: 3,4,8,
Tokens: 4,5,6,
Tokens: 4,5,7,
Tokens: 4,5,8,
Tokens: 2,3,6,
Tokens: 2,3,7,
Tokens: 2,3,8,
Tokens: 3,4,6,
Tokens: 3,4,7,
Tokens: 3,4,8,
Tokens: 4,5,6,
Tokens: 4,5,7,
Tokens: 4,5,8,
Tokens: 3,3,6,
Tokens: 3,3,7,
Tokens: 3,3,8,
Tokens: 3,4,6,
Tokens: 3,4,7,
Tokens: 3,4,8,
Tokens: 4,5,6,
Tokens: 4,5,7,
Tokens: 4,5,8,
所以,你看,有些组合是正确的(1,3,6),有些组合是不正确的(4,5,8),有些组合完全缺失(2,4,8,..)如何解决这个问题?地方的数量和地方的 token 数量可能会有所不同,我只使用了 3 个地方,因为有 2 个地方可以工作,但如果地方更多,它就会有问题。 谢谢。
最佳答案
你的算法几乎是正确的。我认为您不需要返回 true
或 false
并在获得 true
时停止当前迭代。我修改了你的方法Func
:
public static void Func( List<Place> places, int index, Deque<Integer> tokens) {
if (index == places.size()) {
// if control reaches here, it means that we've recursed through a particular combination
// ( consisting of exactly 1 token from each place ), and there are no more "places" left
String outputTokens = "";
for (int token : tokens) {
outputTokens += token + ",";
}
System.out.println("Tokens: "+outputTokens);
} else {
Place p = places.get(index);
for (int token : p.tokens) {
tokens.addLast(token);
Func(places, index+1, tokens);
token.removeLast();
}
}
}
我用了Deque因为它提供了方便的 removeLast
方法来删除最后添加的 token 。您可以将 LinkedList
作为 Deque
的实现传递。
更新
List<List<Integer>> combinations;
// Instead of printing result:
List<Integer> copy = new ArrayList<Integer>(tokens);
combinations.add(copy);
关于java - N 个列表的排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10062244/