Java: Algorithmus zum Platzieren aller möglichen Kombinationen eines Satzes von Ganzzahlen in einer Liste von Matrizen

Question

Ich versuche ein Programm zu entwickeln, das eine Menge von Knoten und eine Gruppe von Menschen beide Ganzzahlen als Schlüssel haben.

Ich muss alle möglichen Kombinationen finden, damit die Leute durch alle Knoten gehen können. Eine einzelne Person kann zu allen Knoten selbst gehen oder durch verschiedene Personen geteilt werden.

Da die Leute homogen sind, gehen zwei Leute durch die gleichen Knoten in der gleichen Reihenfolge, es würde nur als eine Lösung gezählt werden.

Zum Beispiel Sol: Person 0 = [1], Person1 = [2], und Person 2 = [3] entspricht Sol: Person 0 = [2], Person 1 = [1] und Person 2 = [3] oder Sol: Person 0 = [1], Person 1 = [3, 2], Person 2 = null entspricht Sol:, Person 1 = [3, 2], Person 1 = null, Person 2 = [1].

Ich verwende eine Liste der Ganzzahl-Matrix Sol, um alle möglichen Pfade zu speichern Integer [Person] [Knoten]. Also möchte ich die Lösung entweder in einem Set oder in einer Liste speichern. Das wäre Set oder List.

Also ist Sol [0] = gleich allen Knoten, die die Person Nummer 0 durchläuft.

Wenn wir 3 Personen haben (0,1,2) und 3 (1,2,3) Knoten alle möglichen Lösungen sind:

> 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 

Mit Blick auf das Problem meiner Ausgangsidee beginnen sollte das Hinzufügen all die Pfade für die Person 0, die alle Knoten verwendet, die alle Knoten außer 1 vom Pfad der Person 0 nimmt und zur Person 1 hinzufügt, dann die alle Knoten außer 1 von der Person 0 nimmt und sie der Person hinzufügt 1 .. und so weiter.

Dann würde ich die gleiche Funktion aufrufen, die verwendet wird, um die Pfade von Person 0 und Person 1 kombiniert zu generieren und sie für Person 1 (mit den zuvor erzeugten Pfaden) und Person 2 aufzurufen. Also wäre es ideal für ein rekursives Algortihm (meiner Meinung nach).

Ich habe alle möglichen Lösungen, wenn ich zwei Leute habe, und ich bin fest, wie man es für eine unbegrenzte Anzahl von Menschen und Knoten implementieren.

Code:

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 

     } 
    } 
} 

Die Klasse Sol eine Klasse nur enthält ein Integer [] [] sol

ich nur eine Matrix verwenden, und ich ändere es die ganze Zeit, weil ich JVM speichern möchte Erinnerung.

Ich frage mich, ob mir jemand mit meiner Herangehensweise helfen oder mir eine andere Idee geben könnte, wie ich das Problem lösen könnte.

Vielen Dank.

Answer 1

Nach meinem eigenen Vorschlag aus dem Kommentar entschied ich, dass in einer kanonischen Lösung alle Personen, die einen oder mehrere Knoten besuchen, zuerst sind, und alle Personen, die keine Knoten besuchen, kommen als letzte. Die Personen, die die Knoten besuchen, werden nach dem ersten Knoten sortiert, den sie besuchen. Abgesehen davon habe ich meine eigene Lösung von Grund auf geschrieben, anstatt Ihre zu verwenden. Meine Lösung könnte effizienter gestaltet werden, indem der Suchbaum an einigen Stellen beschnitten wird; aber es druckt die gleichen 13 Lösungen, die Sie in der Frage gegeben haben.

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); 
     } 
    } 

}