如何从一组元素中获取组合？

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] 等同于 [A, B, D, C]。

我在 C++ 中找到了这个例子

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

但是我无法复制它。

有什么建议可以解决这个问题吗？

PD：我正在使用 Python，但我对算法比语言更感兴趣。

Answer 1

[哎呀...当我发布答案时，C++ 标签消失了]

[编辑了更多示例，包括使用 char]

代码中注释：

#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]

Answer 2

对于任何组合数学问题，最好的编程方法是找出计数参数的递推关系。在组合的情况下，递推关系只是 C(n, k) = C(n - 1, k - 1) + C(n - 1, k)。但这到底是什么意思呢？请注意，C(n - 1, k - 1) 意味着我们已经获取了数组的第一个元素，并且需要从其他 n - 1 个元素中再添加 k - 1 个元素。类似地，C(n - 1, k) 意味着我们不会选择数组的第一个元素作为 k 个元素之一。但请记住，如果 k 为 0，则 C(n, k) = 1，否则如果 n 为 0，则 C(n, k) = 0。在我们的问题中，k == 0 将 return 集合包含空集，否则如果n == 0，我们将return空集。考虑到这一点，代码结构将如下所示：

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

现在，可以通过执行记忆来优化此功能（但这可以留给您作为练习，reader）。作为额外的练习，你能从它的计数关系开始勾勒出置换函数的样子吗？

提示： 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)

如何从一组元素中获取组合？

How to get combinations from set of elements?

combinations

permutation

combinatorics