我正在尝试开发一个程序，给定一组节点和一组人都将整数作为键。
我需要找到所有可能的组合，让人们通过所有节点。一个人可以自己去所有的节点，也可以由不同的人分流。
由于人是同质的，所以两个人以相同的顺序通过相同的节点，因此只能算作一个解决方案。
例如 Sol: Person 0= [1], Person1= [2], and Person 2= [3] 等价于 Sol: Person 0 = [2], Person 1 = [1] and Person 2 = [3] 或 Sol: Person 0= [1], Person 1= [3, 2], Person 2= null 将等同于 Sol: , Person 1= [3, 2], Person 1= null ,Person 2= [1].
我使用整数矩阵 Sol 的列表来存储所有可能的路径 Integer[person][nodes]。所以我想将解决方案存储在集合或列表中。那将是 Set 或 List。
所以 Sol[0]= 将等于 0 号人经过的所有节点。
如果我们有 3 个人(0,1,2)和 3(1,2,3)个节点，所有可能的解决方案将是:
> Sol 1:
Person 0= [1]
Person 1= [2]
Person 2= [3]
>Sol 2:
Person 0= [3]
Person 1= [2, 1]
Person 2= null
>Sol 3:
Person 0= [3]
Person 1= [1, 2]
Person 2= null
>Sol 4:
Person 0= [1]
Person 1= [3, 2]
Person 2= null
>Sol 5:
Person 0 = [1]
Person 1= [2, 3]
Person 2= null
>Sol 6:
Person 0 = [2]
Person 1= [1, 3]
Person 2= null
>Sol 7:
Person 0 = [2]
Person 1= [3, 1]
Person 2= null
>Sol 8:
Person 0 = [3, 2, 1]
Person 1= null
Person 2= null
>Sol 9:
Person 0 = [1, 2, 3]
Person 1= null
Person 2= null
>Sol 10:
Person 0 = [3, 1, 2]
Person 1= null
Person 2= null
>Sol 11:
Person 0 = [2, 1, 3]
Person 1= null
Person 2= null
>Sol 12:
Person 0 = [1, 3, 2]
Person 1= null
Person 2= null
>Sol 13:
Person 0 = [2, 3, 1]
Person 1= null
Person 2= null
面对这个问题，我最初的想法是开始使用所有节点添加人 0 的所有路径，从人 0 的路径中取出除 1 之外的所有节点并添加到人 1，然后获取所有从人 0 中除 1 之外的节点，并将它们添加到人 1.. 等等。
然后我将调用用于从 Person 0 和 Person 1 组合生成路径的相同函数，并为 Person 1(使用之前生成的路径)和 Person 2 调用它。因此它对于递归算法(在我的意见)。
当我有两个人时，我得到了所有可能的解决方案，但我对如何为无限数量的人和节点实现它感到困惑。
代码:
public static void function(List<Sol> solutions, int startingPerson, Integer[] people, List<Integer> Numbers, Sol part) {
Set<List<Integer>> result;
Set<List<Integer>> resResult;
int i = 0;
for (Integer j = Numbers.size(); j >= 0; j--) {
if (j == 1 && Numbers.size() <= people.length) {
for (int l = startingPerson; l < Numbers.size() + startingPerson; l++) {
Integer[] in2 = new Integer[1];
in2[0] = Numbers.get(l - startingPerson);
part.getSol()[l] = in2;
}
Arrays.fill(part.getSol(), null);
solutions.add(org.apache.commons.lang3.SerializationUtils.clone(part));
Arrays.fill(part.getSol(), null);
}
/*We get all combinations (order not important) of a certain number of the nodes*/
Combinations it = new Combinations(Numbers, i);
Iterator<List<Integer>> s = it.iterator();
Set<List<Integer>> l2 = new HashSet<>();
while (s.hasNext()) {
List<Integer> listares = s.next();
l2.add(listares);
}
/*In l2 we have all the combination so loop them to add them to the paths*/
for (List<Integer> l3 : l2) {
/*We get all possible permutations for the numbers of the combination */
result = permute(l3);
/*We loop all possible permutations*/
for (List<Integer> l4 : result) {
int k = startingPerson;
ArrayList<Integer> res = new ArrayList<>(Numbers);
res.removeAll(l4);
Integer[] array = new Integer[l4.size()];
l4.toArray(array);
//*We get all the permutations from res numbers*//
resResult = permute(res);
//*So we won't repeat same paths*//
if (!res.isEmpty() && (res.size() <= Math.nextUp(Numbers.size() / 2))) {
for (List<Integer> l5 : resResult) {
Integer[] array2 = new Integer[l5.size()];
l5.toArray(array2);
part.getSol()[k] = array2;
}
}
/*Means that we are only using a person to go through all the nodes*/
if (res.isEmpty()) {
part.getSol()[k] = array;
solutions.add(org.apache.commons.lang3.SerializationUtils.clone(part));
Arrays.fill(part.getSol(),null);
/*More than one person to go through the nodes*/
} else if (res.size() <= Math.nextUp(Numbers.size() / 2)) {
part.getSol()[k + 1] = array;
solutions.add(org.apache.commons.lang3.SerializationUtils.clone(part));
part.getSol()[k + 1] = null;
k++;
/*We only can take numbers from the combination if we have more than one element */
/*if(array.length>1) {
function(solutions, k, people, l4, part);
}*/
}
}
}
i++;
}
}
public static Set<List<Integer>> permute(List<Integer> ls) {
// we use a Set of Sets rather than a list of arrays
// because Sets support adding in the middle
// and track current length
Set<List<Integer>> permutations = new HashSet<>();
// Add an empty Set so that the middle for loop runs
permutations.add(new ArrayList<>());
for (int i = 0; i < ls.size(); i++) {
// create a temporary container to hold the new permutations
// while we iterate over the old ones
Set<List<Integer>> current = new HashSet<>();
for (List<Integer> permutation : permutations) {
for (int j = 0, n = permutation.size() + 1; j < n; j++) {
List<Integer> temp = new ArrayList<>(permutation);
temp.add(j, ls.get(i));
current.add(temp);
}
}
permutations = new HashSet<>(current);
}
return permutations;
}
public class Combinations implements Iterable<List<Integer>> {
private List<Integer> lista;
private Integer k;
public Combinations(List<Integer> s, Integer k) {
lista = s;
this.k = k;
}
@Override
public Iterator<List<Integer>> iterator() {
return new IteratorCombn(lista, k);
}
private class IteratorCombn implements Iterator<List<Integer>> {
private int actualSize, maxresult;
private Integer curIndex;
private Integer[] result;
private int[] indices;
private Integer[] arrayList;
private List<Integer> elem = null;
public IteratorCombn(List<Integer> s, Integer k) {
actualSize = k;// desde donde
curIndex = 0;
maxresult = k;
arrayList = new Integer[s.size()];
for (int i = 0; i < arrayList.length; i++) {
arrayList[i] = s.get(i);
}
this.result = new Integer[actualSize < s.size() ? actualSize : s.size()];
indices = new int[result.length];
for (int i = 0; i < result.length; i++) {
indices[i] = result.length - 2 - i;
}
}
public boolean hasNext() {
elem = null;
while ((elem == null && curIndex != -1)) {
if(indices.length==0){
return false;
}
indices[curIndex]++;
if (indices[curIndex] == (curIndex == 0 ? arrayList.length: indices[curIndex - 1])) {
indices[curIndex] = indices.length - curIndex - 2;
curIndex--;
} else {
result[curIndex] = arrayList[indices[curIndex]];
if (curIndex < indices.length - 1)
curIndex++;
else {
elem = new ArrayList<>(result.length);
for (Integer s : result) {
elem.add(s);
}
}
}
}
if (elem == null) {
if (actualSize < maxresult) {
actualSize++;
this.result = new Integer[actualSize < arrayList.length ? actualSize
: arrayList.length];
indices = new int[result.length];
for (int i = 0; i < result.length; i++) {
indices[i] = result.length - 2 - i;
}
curIndex = 0;
return this.hasNext();
} else {
return false;
}
} else {
return true;
}
}
@Override
public List<Integer> next() {
return elem;
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
}
}
Sol 类是一个只包含 Integer[][] sol 的类
我只使用一个矩阵，并且一直在更改它，因为我想节省 JVM 内存。
我想知道是否有人可以帮助我解决问题，或者给我另一个解决问题的想法。
谢谢。
最佳答案
根据评论中我自己的建议，我决定在规范解决方案中，所有访问一个或多个节点的人都排在第一位，而没有访问任何节点的人排在最后。访问节点的人按他们访问的第一个节点排序。除此之外，我从头开始编写了自己的解决方案，而不是使用您的解决方案。通过在几个地方修剪搜索树，我的解决方案可以变得更有效率；但它确实打印了您在问题中给出的相同的 13 个解决方案。
public class Combine {
public static final int nNodes = 3;
public static final int nPersons = 3;
// nodes
private Node[] nodes;
private int nUnvisitedNodes = nNodes;
// solution
private Node[][] sol = new Node[nPersons][];
// no of solutions already found and printed
int nSolutions = 0;
public Combine() {
// init nodes
nodes = new Node[nNodes];
for (int nix = 0; nix < nodes.length; nix++) {
nodes[nix] = new Node(nix + 1); // node names are 1-based
}
// search for solutions -- person 0 first
tryPerson0();
}
private void tryPerson0() {
if (nUnvisitedNodes == 0) { // done
printSolution();
} else {
// assuming this is not the last person, this person may visit 1 through nUnvisitedNodes nodes
// (in a canonical solution person 0 cannot visit 0 nodes)
int maxVisits = nUnvisitedNodes;
for (int nNodesToVisit = 1; nNodesToVisit <= maxVisits; nNodesToVisit++) {
sol[0] = new Node[nNodesToVisit];
tryNode(0, sol[0], 0);
sol[0] = null;
}
}
}
private void tryPerson(int person) {
assert person > 0;
if (nUnvisitedNodes == 0) { // solution complete
printSolution();
} else {
if (person < nPersons) { // still persons to try
if (person == nPersons - 1) { // this is the last person
// person must visit all remaining nodes
// in a canonical solution, first node must be greater than first node visited by previous person
int nNodesToVisit = nUnvisitedNodes;
sol[person] = new Node[nNodesToVisit];
tryNodeWithMininum(person, sol[person], 0, sol[person - 1][0].name + 1);
sol[person] = null;
} else {
// since this is not the last person, this person may visit 1 through nUnvisitedNodes nodes
// in a canonical solution, first node must be greater than first node visited by previous person
int maxVisits = nUnvisitedNodes;
for (int nNodesToVisit = 1; nNodesToVisit <= maxVisits; nNodesToVisit++) {
sol[person] = new Node[nNodesToVisit];
tryNodeWithMininum(person, sol[person], 0, sol[person - 1][0].name + 1);
sol[person] = null;
}
}
}
}
}
private void tryNode(int person, Node[] personSol, int nix) {
if (nix == personSol.length) { // this person's solution complete
tryPerson(person + 1);
} else {
for (Node candidateNode : nodes) {
if (candidateNode.visit()) {
personSol[nix] = candidateNode;
tryNode(person, personSol, nix + 1);
personSol[nix] = null;
candidateNode.unvisit();
}
}
}
}
private void tryNodeWithMininum(int person, Node[] personSol, int nix, int minNodeName) {
for (Node candidateNode : nodes) {
if (candidateNode.getName() >= minNodeName) {
if (candidateNode.visit()) {
personSol[nix] = candidateNode;
tryNode(person, personSol, nix + 1);
personSol[nix] = null;
candidateNode.unvisit();
}
}
}
}
private void printSolution() {
nSolutions++;
System.out.println("> Sol " + nSolutions);
for (int pix = 0; pix < nodes.length; pix++) {
System.out.println("Person " + pix + " = " + Arrays.toString(sol[pix]));
}
System.out.println();
}
public static void main(String[] args) {
new Combine();
}
private class Node {
int name;
boolean visited = false;
public Node(int name) {
this.name = name;
}
/** visits node if not already visited */
public boolean visit() {
if (visited) {
return false;
} else {
visited = true;
nUnvisitedNodes--;
return true;
}
}
/** undoes visit (that is, backtracks) */
public void unvisit() {
assert visited : name;
nUnvisitedNodes++;
visited = false;
}
public int getName() {
return name;
}
@Override
public String toString() {
return String.valueOf(name);
}
}
}
关于Java:将一组整数的所有可能组合放在矩阵列表中的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37634380/