R: Permutationen und Kombinationen mit/ohne Ersatz und für unterschiedliche/nicht eindeutige items/multiset

In diesem thread, ich versuche alle Häufig gestellten Fragen und Ihre Antworten hier. Ich hoffe, dies wird nützlich sein für jemanden.

Allgemeine Frage: so erstellen Sie Sequenzen von r Objekte aus n Objekte?

  • Kombination vs permutation.
  • mit Ersatz vs. ohne Ersatz.
  • verschiedene Gegenstände gegen nicht-eindeutige Elemente (multimengen).

Gibt es insgesamt 2^3=8 Fragen von diesem Typ.

[Update]

Josh O ' Brien schlägt vor, dass die 8 Fragen werden auf zwölffache Weise. In der Tat, die "distinct" - Fragen sind in zwölffache Weise, während die "nicht-eindeutigen" Fragen sind nicht im Lieferumfang enthalten. Jedenfalls ist es interessant zu vergleichen, die 8 Fragen hier mit zwölffache Weise. Siehe die Kommentare für weitere Lesungen.

  • Es gibt wohl zwölf Fragen dieser Art.
  • Ja, es ist wirklich hilfreich, zu organisieren und zu denken, all diese unterschiedlichen kombinatorische Objekte. FYI, die meisten von Google ' s erste Seite trifft für "Zwölffache Weise" mehr lesbaren Tabellen/klarer Erklärungen, als die Wikipedia Seite, die ich verlinkte.
  • Vielen Dank für die Informationen. Ich denke, was ich bin fehlt, sind die surjektive Fällen. Richtig..? [update]: es scheint falsch zu sein
  • Du hast Recht, das ist falsch 😉 die Merkmale, Die die 12-fache Klassifizierung basiert sind +/- anders als das, was Sie ausgewählt haben. Für mich mit Abstand der beste Weg, um darüber nachzudenken ist, wie man sich n Kugeln wird in m Urnen. Es gibt drei mögliche Einschränkungen, wie Sie platziert werden können (keine Beschränkung, muss injective, oder muss surjektive), und 4 möglichen Kombinationen der beschriftete/unbeschriftete Kugeln und Urnen. Hier und hier sind 2 Quellen, die das Objektiv, um das problem zu betrachten.
  • Endlich habe ich den herausfinden, den Unterschied zwischen den 8 Fragen hier und zwölffache. Vier der Fragen, die hier in der zwölffache (die "distinct" - Fragen), während die "nicht-typischen" Fragen, die nicht in zwölffache.
  • Hi Randy, ich werde an Sie wenden Ihre gmail-Adresse mit einem Dokument und einer Frage, wenn das okay ist.
  • auf jeden Fall! aber ich kann nicht in der Lage zu Antworten, bis tonite.

InformationsquelleAutor Randy Lai | 2014-03-21
  1. 22

    BEARBEITEN: ich habe aktualisiert die Antwort auf eine effiziente Paket arrangements

    Erste start mit arrangement

    arrangements enthält einige effiziente Generatoren und Iteratoren für Permutationen und Kombinationen. Es hat sich gezeigt, dass arrangements übertrifft die meisten der bestehenden Pakete von ähnlich Art. Einige benchmarks gefunden werden konnte hier.

    Hier sind die Antworten auf die obigen Fragen

    # 1) combinations: without replacement: distinct items

combinations(5, 2)

      [,1] [,2]
 [1,]    1    2
 [2,]    1    3
 [3,]    1    4
 [4,]    1    5
 [5,]    2    3
 [6,]    2    4
 [7,]    2    5
 [8,]    3    4
 [9,]    3    5
[10,]    4    5


# 2) combinations: with replacement: distinct items

combinations(5, 2, replace=TRUE)

      [,1] [,2]
 [1,]    1    1
 [2,]    1    2
 [3,]    1    3
 [4,]    1    4
 [5,]    1    5
 [6,]    2    2
 [7,]    2    3
 [8,]    2    4
 [9,]    2    5
[10,]    3    3
[11,]    3    4
[12,]    3    5
[13,]    4    4
[14,]    4    5
[15,]    5    5



# 3) combinations: without replacement: non distinct items

combinations(x = c("a", "b", "c"), freq = c(2, 1, 1), k = 2)

     [,1] [,2]
[1,] "a"  "a" 
[2,] "a"  "b" 
[3,] "a"  "c" 
[4,] "b"  "c" 



# 4) combinations: with replacement: non distinct items

combinations(x = c("a", "b", "c"), k = 2, replace = TRUE)  # as `freq` does not matter

     [,1] [,2]
[1,] "a"  "a" 
[2,] "a"  "b" 
[3,] "a"  "c" 
[4,] "b"  "b" 
[5,] "b"  "c" 
[6,] "c"  "c" 

# 5) permutations: without replacement: distinct items

permutations(5, 2)

      [,1] [,2]
 [1,]    1    2
 [2,]    1    3
 [3,]    1    4
 [4,]    1    5
 [5,]    2    1
 [6,]    2    3
 [7,]    2    4
 [8,]    2    5
 [9,]    3    1
[10,]    3    2
[11,]    3    4
[12,]    3    5
[13,]    4    1
[14,]    4    2
[15,]    4    3
[16,]    4    5
[17,]    5    1
[18,]    5    2
[19,]    5    3
[20,]    5    4



# 6) permutations: with replacement: distinct items

permutations(5, 2, replace = TRUE)

      [,1] [,2]
 [1,]    1    1
 [2,]    1    2
 [3,]    1    3
 [4,]    1    4
 [5,]    1    5
 [6,]    2    1
 [7,]    2    2
 [8,]    2    3
 [9,]    2    4
[10,]    2    5
[11,]    3    1
[12,]    3    2
[13,]    3    3
[14,]    3    4
[15,]    3    5
[16,]    4    1
[17,]    4    2
[18,]    4    3
[19,]    4    4
[20,]    4    5
[21,]    5    1
[22,]    5    2
[23,]    5    3
[24,]    5    4
[25,]    5    5


# 7) permutations: without replacement: non distinct items

permutations(x = c("a", "b", "c"), freq = c(2, 1, 1), k = 2)

     [,1] [,2]
[1,] "a"  "a" 
[2,] "a"  "b" 
[3,] "a"  "c" 
[4,] "b"  "a" 
[5,] "b"  "c" 
[6,] "c"  "a" 
[7,] "c"  "b" 



# 8) permutations: with replacement: non distinct items

permutations(x = c("a", "b", "c"), k = 2, replace = TRUE)  # as `freq` doesn't matter

      [,1] [,2]
 [1,] "a"  "a" 
 [2,] "a"  "b" 
 [3,] "a"  "c" 
 [4,] "b"  "a" 
 [5,] "b"  "b" 
 [6,] "b"  "c" 
 [7,] "c"  "a" 
 [8,] "c"  "b" 
 [9,] "c"  "c"

    Im Vergleich zu anderen Paketen

    Es gibt einige Vorteile der Verwendung von arrangements über die vorhandenen Pakete.

    1. Integralen Ansatzes: Sie haben nicht zu verwenden, unterschiedliche Pakete für unterschiedliche Methoden.

    2. Ist es sehr effizient. Sehen https://randy3k.github.io/arrangements/articles/benchmark.html für einige benchmarks.

    3. Es ist Speicher, der effizient ist, ist es zu erzeugen in der Lage alle 13! permutation von 1 bis 13, werden vorhandene Pakete nicht tun, weil die Begrenzung der Größe der matrix. Die getnext() Methode der Iteratoren erlauben den Benutzer, um die Vereinbarungen eins nach dem anderen.

    4. Den erzeugten arrangements sind im Wörterbuch, um die gewünschte, für einige Nutzer.

    • Ich glaube, diese Antwort könnte verbessert werden, indem einige Ausgabe erzählt die Geschichte der "Frage".
    • thx für den Kommentar, ich habe einige Ausgänge
    • Diese Antwort ist eine Werbung für Ihr Paket. Wenn du das machst, bitte demonstrieren die verschiedenen Funktionen und warum Sie besser sind als bisherige Methoden. Wie es ist, meiner Meinung nach, diese Frage und Antwort nicht verdrängen alle anderen Fragen über Kombinationen/Permutationen (und wie es aussieht, ist dies Ihre Absicht).
    • Hallo Matthew, leider fühlen Sie sich wie es ist eine Anzeige (in der Tat, es ist :)..), Wenn Sie gehen, um zu sehen, die Versionsgeschichte meiner Antwort, Sie werden sehen, dass die alten Antworten sind mit anderen Paketen. In allem, es gibt kein Paket dabei k-permeation von multi-set finden Sie unter der home-brew-Funktion here. Da ich unzufrieden war mit der vorhandenen Pakete, also beschloss ich zu schreiben mein eigenes Paket.
    • Aber ich Stimme mit Ihnen, ich vergleichen soll mein Paket mit den vorhandenen Pakete.
    • Hallo Matthew, ich habe aktualisiert die Antwort finden Sie, wenn Sie es sieht besser aus jetzt.
    • Könnte ich schlage vor, Sie ändern Ihre Funktion, Namen. Die Funktionen combinations/permutations aus gtools so weit verbreitet sind, Ihr Paket könnte möglicherweise brechen Abhängigkeiten/legacy-code/etc. Bei der Entwicklung der Pakete, die ich gerne mit dem Sprichwort artikuliert @DirkEddelbuettel: "nicht Schaden".
    • Ich denke, es ist im Allgemeinen nicht ein Problem, weil der empfohlene Weg für ein Paket, um eine Funktion aufzurufen, die in einem anderen Paket ist <package>::<function>. Es sei denn, die Skripte sind besorgt, mit ähnlichen Namen sollte man nicht viel Schaden.....IMO.

    InformationsquelleAutor
Schreibe einen Kommentar