Wie erhält man Kombinationen aus Elementen?

Question

Ich brauche alle Kombinationen ohne Wiederholungen aus einem Array zu erzeugen, las ich über es einige, die Rekursion

zu verwenden, schlage ich habe ein Array

arr = [["A"], ["B"], ["C"], ["D"], ["E"], ["F"]] 

ich gelesen, dass ich dieses Problem mit Hilfe von Rekursion gelöst kann wie

function combinations(arr, n, k) 
    //do something 
    //then 
    return combinations(arr, n, k) 

In meinem Fall [A, B, C, D] ist äquivalent zu [A, B, D, C].

fand ich dieses Beispiel in C++

http://www.martinbroadhurst.com/combinations.html

Aber ich es nicht reproduzieren konnten.

Jeder Vorschlag, wie kann ich dieses Problem lösen?

PD: Ich bin mit Python, aber ich mehr daran interessiert, in dem Algorithmus als die Sprache.

Answer 1

Für Kombinatorik Problem, das beste w Um es zu programmieren, müssen Sie die Wiederholungsbeziehung für das Zählargument herausfinden. Im Fall von Kombinationen ist die Rekursion einfach C (n, k) = C (n - 1, k - 1) + C (n - 1, k). Aber was genau bedeutet das? Beachten Sie, dass C (n - 1, k - 1) bedeutet, dass wir das erste Element des Arrays genommen haben und k - 1 mehr Elemente von den anderen n - 1 Elementen benötigen. In ähnlicher Weise bedeutet C (n - 1, k), dass wir das erste Element unseres Arrays nicht als eines der k Elemente auswählen werden. Aber denken Sie daran, dass, wenn k 0 ist, dann C (n, k) = 1, sonst, wenn n 0 ist, dann C (n, k) = 0. In unserem Problem, k == 0 würde einen Satz zurückgeben enthält die leeren set, sonst wenn n == 0, würden wir die leere Menge zurückgeben. Mit diesem Geist ist, würde der Code-Struktur wie folgt aussehen:

def combinations(arr, k): 

    if k == 0: 
     return [[]] 
    elif len(arr) == 0: 
     return [] 

    result = [] 
    chosen = combinations(arr[1:], k - 1) #we choose the first element of arr as one of the k elements we need 
    notChosen = combinations(arr[1:], k) #first element not chosen in set of k elements 
    for combination in chosen: 
     result.append([arr[0]] + combination) 
    for combination in notChosen: 
     result.append(combination) 
    return result 

Nun kann diese Funktion durch Ausführen memoization optimiert werden (aber das kann als eine Übung Ihnen überlassen werden, der Leser). Können Sie als zusätzliche Übung skizzieren, wie die Permutationsfunktion von ihrer Zählbeziehung aus aussehen würde?

Hinweis: P (n, k) = C (n, k) k! = [C (n - 1, k - 1) + C (n - 1, k)] k! = P (n - 1, k - 1) k + P (n - 1, k)

Answer 2

[Heck ... als ich die Antwort geschrieben, die C++ Tag ging weg]

[mehr Beispiele Edited, einschließlich der Verwendung von char]

Kommentare im Code:

#include <vector> 

// Function that recursively does the actual job 
template <typename T, typename Function> void doCombinations(
    size_t num, const std::vector<T>& values, 
    size_t start, std::vector<T>& combinationSoFar, 
    Function action 
) { 
    if(0==num) { // the entire combination is complete 
    action(combinationSoFar); 
    } 
    else { 
    // walk through with the current position to the right, 
    // taking care to let enough walking room for the rest of the elements 
    for(size_t i=start; i<values.size()+1-num; i++) { 
     // push the current value there 
     combinationSoFar.push_back(values[i]); 

     // recursive call with one less element to enter combination 
     // and one position to the right for the next element to consider 
     doCombinations(num-1, values, i+1, combinationSoFar, action); 

     // pop the current value, we are going to move it to the right anyway 
     combinationSoFar.pop_back(); 
    } 
    } 
} 

// function for the user to call. Prepares everything needed for the 
// doCombinations 
template <typename T, typename Function> 
void for_each_combination(
    size_t numInCombination, 
    const std::vector<T>& values, 
    Function action 
) { 
    std::vector<T> combination; 
    doCombinations(numInCombination, values, 0, combination, action); 
} 

// dummy do-something with the vector 
template <typename T> void cout_vector(const std::vector<T>& v) { 
    std::cout << '['; 
    for(size_t i=0; i<v.size(); i++) { 
    if(i) { 
     std::cout << ","; 
    } 
    std::cout << v[i]; 
    } 
    std::cout << ']' << std::endl; 
} 

// Assumes the T type supports both addition and ostream << 
template <typename T> void adder(const std::vector<T>& vals) { 
    T sum=static_cast<T>(0); 
    for(T v : vals) { 
    sum+=v; 
    } 
    std::cout << "Sum: " << sum << " for "; 
    cout_vector(vals); 
} 

int main() { 
    std::cout << "Char combinations" << std::endl; 
    std::vector<char> char_vals{'A', 'B', 'C', 'D', 'E'}; 
    for_each_combination(3, char_vals, cout_vector<char>); 

    std::cout << "\nInt combinations" << std::endl; 
    std::vector<int> int_vals{0, 1, 2, 3, 4}; 
    for_each_combination(3, int_vals, cout_vector<int>); 

    std::cout <<"\nFloat combination adder" << std::endl; 
    std::vector<float> float_vals{0.0, 1.1, 2.2, 3.3, 4.4}; 
    for_each_combination(3, float_vals, adder<float>); 
    return 0; 
} 

Ausgang:

Char combinations 
[A,B,C] 
[A,B,D] 
[A,B,E] 
[A,C,D] 
[A,C,E] 
[A,D,E] 
[B,C,D] 
[B,C,E] 
[B,D,E] 
[C,D,E] 

Int combinations 
[0,1,2] 
[0,1,3] 
[0,1,4] 
[0,2,3] 
[0,2,4] 
[0,3,4] 
[1,2,3] 
[1,2,4] 
[1,3,4] 
[2,3,4] 

Float combination adder 
Sum: 3.3 for [0,1.1,2.2] 
Sum: 4.4 for [0,1.1,3.3] 
Sum: 5.5 for [0,1.1,4.4] 
Sum: 5.5 for [0,2.2,3.3] 
Sum: 6.6 for [0,2.2,4.4] 
Sum: 7.7 for [0,3.3,4.4] 
Sum: 6.6 for [1.1,2.2,3.3] 
Sum: 7.7 for [1.1,2.2,4.4] 
Sum: 8.8 for [1.1,3.3,4.4] 
Sum: 9.9 for [2.2,3.3,4.4]