我正在尝试开发一个程序，该程序给定了一组节点和一组人都以整数为键。
我需要找到所有可能的组合，以使人们能够遍历所有节点。一个人可以自己去所有节点，也可以由不同的人分开。
由于人员是同质的，因此两个人以相同的顺序进入相同的节点，这将仅被视为一个解决方案。
例如Sol：人员0 = [1]，人员1 = [2]和人员2 = [3]等效于Sol：人员0 = [2]，人员1 = [1]和人员2 = [3]或Sol：人员0 = [1]，人员1 = [3，2]，人员2 = null等同于Sol :，人员1 = [3，2]，人员1 = null，人员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从人员0并将其添加到人员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);
}
}
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句