Как получить комбинации из набора элементов?

Question

мне нужно генерировать все комбинации без повторений из массива, я читал некоторые об этом, что предлагает использовать рекурсию

У меня есть массив

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

я прочитал, что я могу решить эту проблему, используя рекурсию как

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

в моем случае [A, B, C, D] эквивалентно [А, в, D, C].

Я нашел этот пример в C++

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

Но я не мог воспроизвести его.

Любое предложение, как я могу это решить?

PD: Я использую Python, но меня больше интересует алгоритм, чем язык.

Answer 1

Для любой задачи комбинаторика, лучший ш Чтобы запрограммировать это, нужно выяснить отношение повторения для аргумента подсчета. В случае комбинаций рекуррентное соотношение является просто C (n, k) = C (n - 1, k - 1) + C (n - 1, k). Но что это значит? Обратите внимание, что C (n - 1, k - 1) означает, что мы взяли первый элемент массива и нуждаемся в k - еще 1 элементе от других n - 1 элементов. Аналогично, C (n - 1, k) означает, что мы не будем выбирать первый элемент нашего массива как один из k элементов. Но помните, что если k равно 0, то C (n, k) = 1, иначе если n равно 0, то C (n, k) = 0. В нашей задаче k == 0 вернет набор , содержащий пустой set, else, если n == 0, мы вернем пустое множество. Принимая это во внимание, структура коды будет выглядеть следующим образом:

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 

Теперь эта функция может быть оптимизирована путем выполнения запоминания (но это может быть оставлено в качестве упражнения для вас, читателя). Как дополнительное упражнение, можете ли вы набросать, как будет выглядеть функция перестановки, начиная с отношения счета?

Подсказка: 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

[Хек ... к тому времени, я отправил ответ, то C++ тег ушел]

[Отредактировано с большим количеством примеров, в том числе с использованием полукокса]

Комментарии в коде:

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

Выход:

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]