Algorithmus zur Rückgabe aller Kombinationen von k Elementen aus n

Question

Ich möchte eine Funktion schreiben, die ein Array von Buchstaben als Argument und eine Anzahl von diesen Buchstaben zur Auswahl nimmt.

Angenommen, Sie stellen ein Feld mit 8 Buchstaben zur Verfügung und möchten 3 Buchstaben daraus auswählen. Dann sollten Sie erhalten:

8! / ((8 - 3)! * 3!) = 56

Arrays (oder Wörter), die aus jeweils 3 Buchstaben bestehen.

Answer 1

Der folgende rekursive Algorithmus wählt alle k-Element-Kombinationen aus einer geordneten Menge aus:

• wählen Sie das erste Element i Ihrer Kombination
• Mähdrescher i mit jeder der Kombinationen von k-1 Elemente, die rekursiv aus der Menge der Elemente ausgewählt werden, die größer sind als i .

Iterieren Sie die obigen Schritte für jede i im Set.

Es ist wichtig, dass Sie den Rest der Elemente größer wählen als i , um Wiederholungen zu vermeiden. Auf diese Weise wird [3,5] nur einmal ausgewählt, als [3] kombiniert mit [5], anstatt zweimal (die Bedingung eliminiert [5] + [3]). Ohne diese Bedingung erhalten Sie Variationen anstelle von Kombinationen.

Answer 2

Kurzes Beispiel in Python:

def comb(sofar, rest, n):
    if n == 0:
        print sofar
    else:
        for i in range(len(rest)):
            comb(sofar + rest[i], rest[i+1:], n-1)

>>> comb("", "abcde", 3)
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde

Zur Erläuterung wird die rekursive Methode anhand des folgenden Beispiels beschrieben:

Beispiel: A B C D E
Alle Kombinationen von 3 wären:

• A mit allen 2er-Kombinationen aus dem Rest (B C D E)
• B mit allen 2er-Kombinationen aus dem Rest (C D E)
• C mit allen 2er-Kombinationen aus dem Rest (D E)

Answer 3

In C++ erzeugt die folgende Routine alle Kombinationen der Länge distance(first,k) zwischen dem Bereich [first,last):

#include <algorithm>

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

Sie kann wie folgt verwendet werden:

#include <string>
#include <iostream>

int main()
{
    std::string s = "12345";
    std::size_t comb_size = 3;
    do
    {
        std::cout << std::string(s.begin(), s.begin() + comb_size) << std::endl;
    } while (next_combination(s.begin(), s.begin() + comb_size, s.end()));

    return 0;
}

Dadurch wird Folgendes gedruckt:

123
124
125
134
135
145
234
235
245
345

Answer 4

Ich fand diesen Thread nützlich und dachte, ich würde eine Javascript-Lösung hinzufügen, die Sie in Firebug einfügen können. Je nach Ihrer JS-Engine, könnte es ein wenig Zeit, wenn die Startzeichenfolge ist groß.

function string_recurse(active, rest) {
    if (rest.length == 0) {
        console.log(active);
    } else {
        string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));
        string_recurse(active, rest.substring(1, rest.length));
    }
}
string_recurse("", "abc");

Die Ausgabe sollte wie folgt aussehen:

abc
ab
ac
a
bc
b
c

Answer 5

static IEnumerable<string> Combinations(List<string> characters, int length)
{
    for (int i = 0; i < characters.Count; i++)
    {
        // only want 1 character, just return this one
        if (length == 1)
            yield return characters[i];

        // want more than one character, return this one plus all combinations one shorter
        // only use characters after the current one for the rest of the combinations
        else
            foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
                yield return characters[i] + next;
    }
}