Alle Kombinationen der Paare in einem Satz

Möchte ich berechne alle möglichen Listen von Paaren, Sie könnte einen Satz. Zum Beispiel:

input = [1, 2, 3, 4, 5, 6]

output = {[(1,2), (3,4), (5,6)],
          [(2,3), (4,5), (1,6)],
          [(2,4), (1,3), (5,6)],
          [...], .... }

Hinweis: in diesem Beispiel sind nur einige zufällige Dinge, die in der Ausgabe, die meisten entfernt. Ich kümmern sich nicht um die Reihenfolge der Listen oder die Paare innerhalb dieser Listen.

Ich denke, es wäre (n-1)(n-3)(n-5)... möglich, Listen von Paaren. Zuerst dachte ich, Sie könnte alle Permutationen der Eingabe-Liste. Mit all diesen Permutationen könnten Sie das erste mit dem zweiten Element und der Dritte mit der vierten. Aber offensichtlich ist das sehr ineffizient, weil Sie machen würde n! Elemente in der Liste und Sie würden nur noch (n-1)(n-3)(n-5).... Konnte einige mir einen Tipp geben wie dies zu tun ist effizienter? Gibt es einen bekannten Algorithmus oder was wären die richtigen Stichworte, um eine Suche mit? Ich möchte, um dies zu implementieren, in JAVA, also, wenn Sie wollen, um die Verwendung der Collections-Klasse in JAVA kein problem 🙂

Um deutlicher zu sein: die Eingabe immer aus einer geraden Anzahl von Elementen, so dass alle Paare in einer Liste zusammen, sind alle Elemente in der Eingabe.

Edit:
Ich schauen mal für alle Antwort. Jetzt habe ich zu arbeiten-code-vielen Dank dafür. Aber ich brauche es für eine Eingabe mit der Größe n = 26 :(. Ich habe nicht alles umgesetzt, aber ich denke, es wird für eine Weile laufen :(.

  • Sie sind gefragt, für Partitionen, die in Paare? Es wird mehr als n(n-1)/2 von denen. Es werde C(n,2) * C(n-2,2)*...
  • Deine Ausgabe zeigt (5,6) zweimal aufgeführt. Ist das nur ein Fehler???
  • Es gibt n!/[2^(n/2)*(n/2)!] verschiedenen Paarungen, so dass Ihre n! die Lösung ist nicht so eine Verschwendung.
  • Ich habe bearbeitet die Höhe der verschiedenen Paarungen und ich bin mir ziemlich sicher, dass es nun korrigieren. Suchen Sie die Erklärung unten.
InformationsquelleAutor martijnn2008 | 2014-02-13
  1. 4

    Wenn ich das richtig verstanden, eine rekursive Lösung dieses Problems sollte ganz einfach sein:

    • Entfernen Sie das erste element A aus der Menge
    • Für jedes verbliebene element B:
      • Entfernen element B aus der Menge
      • Ein paar (A,B), und speichern Sie es als Teil der aktuellen Lösung
      • Tun, die Rekursion mit der restlichen Menge. Dies wird fügen Sie mehrere Paare, um die aktuelle Lösung. Wenn es keine weiteren Elemente Links in die setzen, dann speichern Sie die aktuelle Lösung als eine der letzten Lösungen.
      • Add-element B der Satz
    • Add-element Eine set

    Den Teil mit hinzufügen und entfernen der Elemente ist nicht wirklich enthalten in diesem Beispiel die Umsetzung, denn es erstellt eine Liste und einen neuen Satz für das iterative und das rekursive aufrufen, aber die Idee sollte klar sein.

    import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class AllPairs
{
    public static void main(String[] args)
    {
        Set<Integer> set = new LinkedHashSet<Integer>(
            Arrays.asList(1,2,3,4,5,6));

        ArrayList<List<List<Integer>>> results = 
            new ArrayList<List<List<Integer>>>();
        compute(set, new ArrayList<List<Integer>>(), results);
        for (List<List<Integer>> result : results)
        {
            System.out.println(result);
        }
    }

    private static void compute(Set<Integer> set,
        List<List<Integer>> currentResults,
        List<List<List<Integer>>> results)
    {
        if (set.size() < 2)
        {
            results.add(new ArrayList<List<Integer>>(currentResults));
            return;
        }
        List<Integer> list = new ArrayList<Integer>(set);
        Integer first = list.remove(0);
        for (int i=0; i<list.size(); i++)
        {
            Integer second = list.get(i);
            Set<Integer> nextSet = new LinkedHashSet<Integer>(list);
            nextSet.remove(second);

            List<Integer> pair = Arrays.asList(first, second);
            currentResults.add(pair);
            compute(nextSet, currentResults, results);
            currentResults.remove(pair);
        }
    }
}
    • Ich habe deinen code getestet und er macht genau das, was ich will.
    InformationsquelleAutor Marco13
  2. 1

    Bearbeiten: Mein voriger post war teilweise falsch. Ich wusste nicht, kümmerte sich um OP ' s Satz "I don' T care über die Reihenfolge der Listen oder die Paare innerhalb dieser Listen".

    Was Sie fordern, sind aufgerufen, eine perfekte Paarung (matching). Die Anzahl der Paare ist n*(n+1)/2, aber die Anzahl der koppeln ist (n-1)*(n-3)*(n-5)*... in der Tat sind die Möglichkeiten

    • wählen, die gepaart ist mit 1: (n-1) Wahl
    • wählen, die gekoppelt ist mit das kleinste Verbleibende element: (n-3) Wahl
    • wählen, die gekoppelt ist mit das kleinste Verbleibende element: (n-5) Wahl
    • ...

    Hier 5*3*1 = 15. Ich bin kein erfahrener java-Benutzer, so Schreibe ich es in Python. Ich bin mit einem rekursiven Algorithmus.

    def pairing(l):
    def rec(l, choice):
        if l == []:
            print choice
        else:
            for j in range(1, len(l)):
                choice1 = choice + [(l[0],l[j])]
                l1 = copy(l)
                del l1[j]
                del l1[0]
                rec(l1, choice1)
    rec(l, [])

    Gibt:

    [(1, 2), (3, 4), (5, 6)]
    [(1, 2), (3, 5), (4, 6)]
    [(1, 2), (3, 6), (4, 5)]
    [(1, 3), (2, 4), (5, 6)]
    [(1, 3), (2, 5), (4, 6)]
    [(1, 3), (2, 6), (4, 5)]
    [(1, 4), (2, 3), (5, 6)]
    [(1, 4), (2, 5), (3, 6)]
    [(1, 4), (2, 6), (3, 5)]
    [(1, 5), (2, 3), (4, 6)]
    [(1, 5), (2, 4), (3, 6)]
    [(1, 5), (2, 6), (3, 4)]
    [(1, 6), (2, 3), (4, 5)]
    [(1, 6), (2, 4), (3, 5)]
    [(1, 6), (2, 5), (3, 4)]

    Hinweis: ich habe nicht versucht, Sie zu optimieren und mit intelligenten Daten-Strukturen. Insbesondere die Verwendung doppelt verkettete Liste kann man vermeiden, kopieren choice und l1.

    • also, wie funktioniert diese produzieren, {2,1} zum Beispiel?
    • (2,1) oder (1,2) sind die gleichen. Wie ich bereits erwähnte I don ' T care über die Bestellung von etwas. Also das sieht gut aus. Danke für deine Erklärung auf der (n-1)(n-3)... Sache, die ich fand, dass auf dem Weg nach Hause, aber du warst schneller mit posten hier 🙂
    InformationsquelleAutor hivert
  3. 0

    Können Sie Guave ist Sets#cartesianProduct

    Set<List<Integer>> product = Sets.cartesianProduct(ImmutableList.of(ImmutableSet.of(1, 2, 3, 4, 5, 6),ImmutableSet.of(1, 2, 3, 4, 5, 6)));

    Ergeben:

    [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]]

    Dann können Sie entfernen Sie Elemente, wie [1, 1] und so weiter

    • Das beantwortet nicht die Frage !
    • Der Ausgang ist nicht das was ich haben will...
    InformationsquelleAutor Алексей
  4. 0

    die erste Sache, die kommen würde, in jemandes Geist ist die Permutaions oder die Kollektionen so, dass Sie bereits erwähnt haben, ist nicht sehr effizient.

    Lassen Sie uns mit einer Frage beginnen, sind Sie komfortabel mit Binär-Zahlen?
    Sie haben zu einer echten Besonderheit, Sie stellen nur zwei Staaten, D. H. das Vorhandensein(1) oder fehlen(0).

    Wenn Sie auf der Suche für eine schnelle Codierung-Lösung, hier gehen Sie. Wenn Sie daran interessiert sind, das Konzept, Lesen Sie weiter:

    public class Test {
public static void main(String[] args) {
    int[] input = new int[] {1, 2, 3, 4, 5, 6};
    Test s = new Test();
    s.method(input);
}

public void method(int [] x){
    for( int i = 0 ; i < 1<<x.length ; i++){

        if( Integer.bitCount(i) == 2){
            System.out.println(x[getIndex(Integer.highestOneBit(i))]+", "+x[getIndex(Integer.lowestOneBit(i))]);


        }
    }
}

private int getIndex(int i ){
    if((i & 0) == 1)
        return 0;
    if((i>>1 & 1) == 1 )
        return 1;
    if((i>>2 & 1) == 1 )
        return 2;
    if((i>>3 & 1) == 1 )
        return 3;
    if((i>>4 & 1) == 1 )
        return 4;
    if((i>>5 & 1) == 1 )
        return 5;
    if((i>>6 & 1) == 1 )
        return 6;
    return 0;
}
}

    Erklärung:
    Lassen Sie uns annehmen, wir haben drei Zeichen (a, b, c) und wir wollen finden, dass alle Paare:

    Nun davon ausgehen, ein drei-bit-integer, lassen Sie uns notieren alle möglichen ganzen zahlen von drei bits:

     000 --- 0
 001 --- 1
 010 --- 2
 011 --- 3
 100 --- 4
 101 --- 5
 110 --- 6
 111 --- 7

    Wählen Sie nun die Zahl mit zwei high-bits also wäre ( 3, 5, 6)
    Wählen Sie nun die Indizes der high-bits aus der ersten Reihe 3, so

    The first pair would be index 1 and 2 - b, c
The second pair would be index 0 and 2 - a, b
The third pair would be index 2 and 1 - a, b
    • Ich schaue nicht in Ihre Lösungen vollständig, die binairy Zeug sieht nett aus, aber shouln ' T verwenden Sie eine Schleife, in der Sie getIndex-Methode? Ich auch wollen, verwenden Sie die Umsetzung nicht nur bei Integer, sondern auch strings. Ich habe einen besseren Blick auf Ihre Antwort kurz.
    • auch Sie können Schleife, aber ich schrieb es nur, um zu vereinfachen. 🙂 Egal, ob Sie möchten, Integer, string oder jede andere Eingabe-array. die Lösung hält.
    • Ich hatte einen besseren Blick auf deinen code, ich verstehe es nicht ganz, aber ich führe auch Ihren code und es nicht zu tun, was es tun sollte.
    InformationsquelleAutor dharam
Schreibe einen Kommentar