计算置换子集
Calculate Permutation Subsets
上下文：
我想解决纸牌游戏。为了减少可能的游戏计算，我使用信息抽象。这导致排列的子集。计算子集就是问题
示例：
给定 2 个玩家，每个玩家从一副 8 张牌中拿 2 张牌。有 1680 个排列。导致相同游戏的一些排列可以从游戏列表中删除以进行计算，例如：
{1,2,3,4} , {1,2,4,3} , {2,1,3,4} , {2,1,4,3} 都会导致相同的游戏，因为这无关紧要玩家以何种顺序收到卡片，重要的是他得到了什么卡片。
所以我可以删除不满足的排列：{a,b,c,d} aFormula with slider to play around.
我的问题是找到一个算法来生成这个子集并且很灵活，这样我就可以在不改变的情况下从 8 中计算出 4 张牌，从 12 中计算出 6 张牌。
编辑：
目前我尝试将子集除以二，然后找到元素递增的所有排列，然后我尝试找到大小为 2
结果的所有排列
示例：
2 来自 {1,2,3,4,5,6,7,8}
{1,2},{1,3}, {7,8}
将结果用于新排列，从忽略相等数字的所有结果中取 2。
可能的结果：
{{1,2},{3,4}}
{{3,4},{1,2}}
解决办法是：
将子集除以二然后求出所有元素递增的排列然后尝试求出结果的所有排列
示例：
4 来自 {1,2,3,4,5,6,7,8}
- 从 8 计算两个元素，得到 {1,2},{1,3} ... {7,8}
- 将结果用于新排列 {{1,2},{1,3}}, {{1,2},{3,4}}
- 为每个新排列创建一个数组 {1,2,1,3}, {1,2,3,4}
- 如果其中所有数字都是唯一的，则对其进行排序并将其推送到结果（{1,2,1,3} 无效，因为它有两个）。
C++ 代码：（未优化）
旧子集
#include <vector>
#include <iostream>
// Requires: sequence from begin to end is sorted
// middle is between begin and end
template <typename Bidi, typename Functor>
void
for_each_permuted_combination (Bidi begin, Bidi middle, Bidi end, Functor func)
{
do
{
func (begin, middle);
std::reverse (middle, end);
}
while (std::next_permutation (begin, end));
}
std::vector<std::vector<uint8_t> >
oldSubset (int subsetSize, std::vector<uint8_t> setOfNumbers)
{
if (subsetSize % 2 != 0)
{
throw std::logic_error{ "only tested for even subsets" };
return {};
}
auto subsets = std::vector<std::vector<uint8_t> >{};
for_each_permuted_combination (setOfNumbers.begin (), setOfNumbers.begin () + subsetSize / 2, setOfNumbers.end (), [&subsets] (auto begin, auto end) {
if (std::is_sorted (begin, end))
{
subsets.push_back (std::vector<uint8_t> (begin, end));
}
});
auto permutations = std::vector<std::vector<uint8_t> >{};
for_each_permuted_combination (subsets.begin (), subsets.begin () + 2, subsets.end (), [&permutations] (auto begin, auto end) {
auto permutation = std::vector<std::vector<uint8_t> > (begin, end);
auto possibleResult = std::vector<uint8_t>{};
std::copy (permutation.front ().begin (), permutation.front ().end (), std::back_inserter (possibleResult));
std::copy (permutation.back ().begin (), permutation.back ().end (), std::back_inserter (possibleResult));
auto copyOfPossibleResult = possibleResult;
std::sort (copyOfPossibleResult.begin (), copyOfPossibleResult.end ());
if (std::adjacent_find (copyOfPossibleResult.begin (), copyOfPossibleResult.end ()) == copyOfPossibleResult.end ())
{
permutations.push_back (possibleResult);
}
});
return permutations;
}
int
main ()
{
auto results = oldSubset (4, { 1, 2, 3, 4, 5, 6});
for(auto const& result:results){
std::copy (result.begin (), result.end (), std::ostream_iterator<int> (std::cout, " "));
std::cout<<std::endl;
}
}
输出
1 2 3 4
1 2 3 5
1 2 3 6
1 2 4 5
1 2 4 6
1 2 5 6
1 3 2 4
1 3 2 5
1 3 2 6
1 3 4 5
1 3 4 6
1 3 5 6
1 4 2 3
1 4 2 5
1 4 2 6
1 4 3 5
1 4 3 6
1 4 5 6
1 5 2 3
1 5 2 4
1 5 2 6
1 5 3 4
1 5 3 6
1 5 4 6
1 6 2 3
1 6 2 4
1 6 2 5
1 6 3 4
1 6 3 5
1 6 4 5
2 3 1 4
2 3 1 5
2 3 1 6
2 3 4 5
2 3 4 6
2 3 5 6
2 4 1 3
2 4 1 5
2 4 1 6
2 4 3 5
2 4 3 6
2 4 5 6
2 5 1 3
2 5 1 4
2 5 1 6
2 5 3 4
2 5 3 6
2 5 4 6
2 6 1 3
2 6 1 4
2 6 1 5
2 6 3 4
2 6 3 5
2 6 4 5
3 4 1 2
3 4 1 5
3 4 1 6
3 4 2 5
3 4 2 6
3 4 5 6
3 5 1 2
3 5 1 4
3 5 1 6
3 5 2 4
3 5 2 6
3 5 4 6
3 6 1 2
3 6 1 4
3 6 1 5
3 6 2 4
3 6 2 5
3 6 4 5
4 5 1 2
4 5 1 3
4 5 1 6
4 5 2 3
4 5 2 6
4 5 3 6
4 6 1 2
4 6 1 3
4 6 1 5
4 6 2 3
4 6 2 5
4 6 3 5
5 6 1 2
5 6 1 3
5 6 1 4
5 6 2 3
5 6 2 4
5 6 3 4
编辑：优化版本
子集
#include <vector>
#include <tuple>
#include <iostream>
#include <numeric>
typedef std::tuple<std::vector<u_int8_t>, std::vector<std::vector<u_int8_t> > > subsetAndCombinations;
// Requires: sequence from begin to end is sorted
// middle is between begin and end
template <typename Bidi, typename Functor>
void
for_each_permuted_combination (Bidi begin, Bidi middle, Bidi end, Functor func)
{
do
{
func (begin, middle);
std::reverse (middle, end);
}
while (std::next_permutation (begin, end));
}
std::vector<std::vector<u_int8_t> >
subsetPermutation (long int subsetSize, std::vector<uint8_t> setOfNumbers)
{
if (subsetSize % 2 != 0) return {};
std::vector<std::vector<u_int8_t> > subsets{};
for_each_permuted_combination (setOfNumbers.begin (), setOfNumbers.begin () + subsetSize / 2, setOfNumbers.end (), [&subsets] (auto begin, auto end) mutable {
if (std::is_sorted (begin, end))
{
subsets.push_back ({ begin, end });
}
});
return subsets;
}
subsetAndCombinations
combinationsFor (std::vector<u_int8_t> const &numbersToCheck, std::vector<std::vector<u_int8_t> > const &subResults, std::vector<u_int8_t> const &numbersToChoseFrom)
{
auto result = std::tuple<std::vector<u_int8_t>, std::vector<std::vector<u_int8_t> > >{};
std::get<0> (result) = numbersToCheck;
std::get<1> (result).reserve (subResults.size ());
std::vector<u_int8_t> numbers (numbersToChoseFrom.size () - numbersToCheck.size ());
std::set_difference (numbersToChoseFrom.begin (), numbersToChoseFrom.end (), numbersToCheck.begin (), numbersToCheck.end (), numbers.begin ());
std::transform (subResults.begin (), subResults.end (), std::back_inserter (std::get<1> (result)), [&numbers] (auto indexes) {
std::transform (indexes.begin (), indexes.end (), indexes.begin (), [&numbers] (auto index) { return numbers[index]; });
return indexes;
});
return result;
}
std::vector<subsetAndCombinations>
subset (long int k, size_t n)
{
auto indexes = std::vector<uint8_t> (n);
std::iota (indexes.begin (), indexes.end (), 0);
auto results = subsetPermutation (k, indexes);
auto subResult = subsetPermutation (k, std::vector<uint8_t> (indexes.begin (), indexes.begin () + static_cast<long int> (n) - (k / 2)));
auto combineResult = std::vector<subsetAndCombinations>{};
for (auto result : results)
{
combineResult.push_back (combinationsFor (result, subResult, indexes));
}
return combineResult;
}
int
main ()
{
auto results = subset (4, 6);
//print results
for (auto const &[subset, combis] : results)
{
for (auto const &combi : combis)
{
std::copy (subset.begin (), subset.end (), std::ostream_iterator<int> (std::cout, " "));
std::copy (combi.begin (), combi.end (), std::ostream_iterator<int> (std::cout, " "));
std::cout << std::endl;
}
std::cout << std::endl;
}
}
edit2：oldSubset 与在 Intel(R) Core(TM) i5-8600K 上使用 catch2 的子集的基准测试 CPU @ 3.60GHz
clang 版本 13.0.0 发布版本
benchmark name samples iterations estimated
mean low mean high mean
std dev low std dev high std dev
-------------------------------------------------------------------------------
subset (4, sixNumbers) 100 8 4.2488 ms
5.12302 us 5.11219 us 5.15303 us
85.5219 ns 37.5917 ns 183.126 ns
oldSubset (4, sixNumbers) 100 1 5.3749 ms
54.1088 us 53.6284 us 55.3097 us
3.60139 us 1.65755 us 7.04574 us
subset (4, eightNumbers) 100 2 4.1362 ms
20.6127 us 20.3747 us 21.221 us
1.80225 us 845.815 ns 3.48066 us
oldSubset (4, eightNumbers) 100 1 24.4414 ms
237.982 us 236.57 us 240.066 us
8.63522 us 6.29346 us 12.1139 us
subset (6, eightNumbers) 100 1 4.107 ms
41.1901 us 41.005 us 41.7309 us
1.48208 us 634.215 ns 3.21124 us
oldSubset (6, eightNumbers) 100 1 149.468 ms
1.49836 ms 1.49526 ms 1.50226 ms
17.5873 us 14.9794 us 22.8566 us
subset (4, tenNumbers) 100 1 6.5134 ms
65.0695 us 64.5343 us 65.9829 us
3.4798 us 2.28411 us 4.82172 us
oldSubset (4, tenNumbers) 100 1 74.4154 ms
754.08 us 752.067 us 756.94 us
12.1161 us 9.50739 us 15.514 us
subset (6, tenNumbers) 100 1 21.2435 ms
209.317 us 207.847 us 211.412 us
8.88665 us 6.72703 us 11.1798 us
oldSubset (6, tenNumbers) 100 1 1.17232 s
11.7905 ms 11.7811 ms 11.8024 ms
53.7095 us 43.4715 us 65.5498 us
subset (8, tenNumbers) 100 1 23.4467 ms
235.972 us 234.262 us 238.712 us
10.8037 us 7.82671 us 16.3172 us
oldSubset (8, tenNumbers) 100 1 6.65554 s
66.7037 ms 66.5035 ms 66.9362 ms
1.09843 ms 954.738 us 1.22926 ms
subset (4, twelveNumbers) 100 1 14.8182 ms
149.715 us 148.325 us 152.211 us
9.22947 us 5.93872 us 14.6366 us
oldSubset (4, twelveNumbers) 100 1 204.43 ms
2.06251 ms 2.05898 ms 2.06644 ms
18.9013 us 14.9089 us 25.4169 us
subset (6, twelveNumbers) 100 1 85.5855 ms
841.024 us 837.534 us 845.313 us
19.7371 us 16.5515 us 24.1813 us
oldSubset (6, twelveNumbers) 100 1 6.65107 s
67.0061 ms 66.9113 ms 67.1053 ms
495.839 us 452.768 us 552.615 us
subset (8, twelveNumbers) 100 1 176.525 ms
1.76037 ms 1.75612 ms 1.76481 ms
22.2971 us 20.032 us 25.2517 us
oldSubset (8, twelveNumbers) 100 1 1.36774 m
819.4 ms 817.476 ms 821.68 ms
10.7189 ms 9.24014 ms 12.3794 ms
subset (10, twelveNumbers) 100 1 196.563 ms
1.94786 ms 1.93109 ms 1.96496 ms
86.618 us 77.6169 us 96.7013 us
oldSubset (10, twelveNumbers) 100 1 6.28968 m
3.83712 s 3.83005 s 3.84504 s
38.1357 ms 33.2592 ms 44.7012 ms
g++ (GCC) 11.1.0 发布版本
benchmark name samples iterations estimated
mean low mean high mean
std dev low std dev high std dev
-------------------------------------------------------------------------------
subset (4, sixNumbers) 100 5 2.2055 ms
4.39944 us 4.38703 us 4.44751 us
106.292 ns 11.2639 ns 244.087 ns
oldSubset (4, sixNumbers) 100 1 5.2325 ms
51.7199 us 51.6355 us 51.9248 us
628.408 ns 315.255 ns 1.25787 us
subset (4, eightNumbers) 100 2 3.473 ms
17.2042 us 17.0591 us 17.8612 us
1.3454 us 169.46 ns 3.18688 us
oldSubset (4, eightNumbers) 100 1 24.246 ms
243.944 us 243.561 us 244.451 us
2.23092 us 1.79177 us 2.77771 us
subset (6, eightNumbers) 100 1 3.6771 ms
37.6169 us 37.4309 us 38.1215 us
1.44523 us 666.679 ns 3.09803 us
oldSubset (6, eightNumbers) 100 1 145.011 ms
1.40323 ms 1.40017 ms 1.40992 ms
22.0044 us 11.2033 us 39.7721 us
subset (4, tenNumbers) 100 1 5.7933 ms
58.8654 us 58.6273 us 59.5799 us
1.9226 us 788.588 ns 4.18631 us
oldSubset (4, tenNumbers) 100 1 79.7406 ms
793.094 us 792.263 us 794.172 us
4.80223 us 3.88654 us 5.93634 us
subset (6, tenNumbers) 100 1 18.3623 ms
188.659 us 188.158 us 190.088 us
3.97281 us 1.77668 us 8.57928 us
oldSubset (6, tenNumbers) 100 1 1.16914 s
11.6407 ms 11.6321 ms 11.6509 ms
47.6677 us 39.6378 us 60.7322 us
subset (8, tenNumbers) 100 1 22.1842 ms
222.242 us 221.612 us 223.478 us
4.32973 us 2.0686 us 8.21289 us
oldSubset (8, tenNumbers) 100 1 6.398 s
63.9016 ms 63.8632 ms 63.9403 ms
196.147 us 177.473 us 221.609 us
subset (4, twelveNumbers) 100 1 12.2964 ms
124.878 us 124.642 us 125.304 us
1.57641 us 1.02773 us 2.91879 us
oldSubset (4, twelveNumbers) 100 1 219.962 ms
2.18378 ms 2.1825 ms 2.18628 ms
8.76462 us 5.40766 us 16.4105 us
subset (6, twelveNumbers) 100 1 74.5191 ms
749.617 us 748.214 us 753.058 us
10.4827 us 5.42864 us 21.6588 us
oldSubset (6, twelveNumbers) 100 1 6.53912 s
65.2901 ms 65.2766 ms 65.3227 ms
100.232 us 50.7812 us 201.115 us
subset (8, twelveNumbers) 100 1 157.06 ms
1.58509 ms 1.58038 ms 1.59278 ms
30.1286 us 21.3724 us 49.5146 us
oldSubset (8, twelveNumbers) 100 1 1.30347 m
775.358 ms 773.562 ms 776.915 ms
8.46007 ms 7.32211 ms 9.60251 ms
subset (10, twelveNumbers) 100 1 189.041 ms
1.89293 ms 1.88865 ms 1.90194 ms
30.2312 us 15.9272 us 58.5911 us
oldSubset (10, twelveNumbers) 100 1 5.27331 m
3.14281 s 3.13666 s 3.14754 s
27.4681 ms 22.0504 ms 33.0537 ms
这是 Python 中的解决方案 - 抱歉，没有时间用 C++ 编写它。 foo 生成器计算纸牌总数和发给玩家的纸牌总和，假设每个玩家收到的纸牌数量相同。然后它会在每次迭代时生成下一个组合。
del_elmts 和 restore_elmts 函数只是为了避免在从牌组中移除玩家 1 的手时将整个数组 P 复制到临时数组中。警告：Python 仍然通过 [:n-k//2] 范围访问生成几乎完整的副本，但在 C++ 中，您可以通过使组合函数更智能一些来避免这种情况。
import itertools
def del_elmts(li,delset):
for i in range(len(delset)-1,-1,-1):
if (delset[i] < len(li)-len(delset)):
li[delset[i]] = li[len(li)-len(delset)+i]
def restore_elmts(li,delset):
for i in delset:
li[i] = i
def foo(n,k):
if k % 2 != 0: raise ValueError
P = list(range(n))
for p in itertools.combinations(P,k//2):
del_elmts(P,p)
for p2 in itertools.combinations(P[:n-k//2],k//2):
yield p+p2
restore_elmts(P,p)
x = foo(6,4)
for y in x:
print(list(map(lambda x: x+1,y)))
PS: 如果你想将它与另一个算法进行比较，你可能需要对输出的前半部分和后半部分进行排序。
上下文： 我想解决纸牌游戏。为了减少可能的游戏计算，我使用信息抽象。这导致排列的子集。计算子集就是问题
示例： 给定 2 个玩家，每个玩家从一副 8 张牌中拿 2 张牌。有 1680 个排列。导致相同游戏的一些排列可以从游戏列表中删除以进行计算，例如： {1,2,3,4} , {1,2,4,3} , {2,1,3,4} , {2,1,4,3} 都会导致相同的游戏，因为这无关紧要玩家以何种顺序收到卡片，重要的是他得到了什么卡片。 所以我可以删除不满足的排列：{a,b,c,d} aFormula with slider to play around.
我的问题是找到一个算法来生成这个子集并且很灵活，这样我就可以在不改变的情况下从 8 中计算出 4 张牌，从 12 中计算出 6 张牌。
编辑： 目前我尝试将子集除以二，然后找到元素递增的所有排列，然后我尝试找到大小为 2
结果的所有排列示例： 2 来自 {1,2,3,4,5,6,7,8} {1,2},{1,3}, {7,8} 将结果用于新排列，从忽略相等数字的所有结果中取 2。 可能的结果： {{1,2},{3,4}} {{3,4},{1,2}}
解决办法是： 将子集除以二然后求出所有元素递增的排列然后尝试求出结果的所有排列
示例： 4 来自 {1,2,3,4,5,6,7,8}
- 从 8 计算两个元素，得到 {1,2},{1,3} ... {7,8}
- 将结果用于新排列 {{1,2},{1,3}}, {{1,2},{3,4}}
- 为每个新排列创建一个数组 {1,2,1,3}, {1,2,3,4}
- 如果其中所有数字都是唯一的，则对其进行排序并将其推送到结果（{1,2,1,3} 无效，因为它有两个）。
C++ 代码：（未优化）
旧子集
#include <vector>
#include <iostream>
// Requires: sequence from begin to end is sorted
// middle is between begin and end
template <typename Bidi, typename Functor>
void
for_each_permuted_combination (Bidi begin, Bidi middle, Bidi end, Functor func)
{
do
{
func (begin, middle);
std::reverse (middle, end);
}
while (std::next_permutation (begin, end));
}
std::vector<std::vector<uint8_t> >
oldSubset (int subsetSize, std::vector<uint8_t> setOfNumbers)
{
if (subsetSize % 2 != 0)
{
throw std::logic_error{ "only tested for even subsets" };
return {};
}
auto subsets = std::vector<std::vector<uint8_t> >{};
for_each_permuted_combination (setOfNumbers.begin (), setOfNumbers.begin () + subsetSize / 2, setOfNumbers.end (), [&subsets] (auto begin, auto end) {
if (std::is_sorted (begin, end))
{
subsets.push_back (std::vector<uint8_t> (begin, end));
}
});
auto permutations = std::vector<std::vector<uint8_t> >{};
for_each_permuted_combination (subsets.begin (), subsets.begin () + 2, subsets.end (), [&permutations] (auto begin, auto end) {
auto permutation = std::vector<std::vector<uint8_t> > (begin, end);
auto possibleResult = std::vector<uint8_t>{};
std::copy (permutation.front ().begin (), permutation.front ().end (), std::back_inserter (possibleResult));
std::copy (permutation.back ().begin (), permutation.back ().end (), std::back_inserter (possibleResult));
auto copyOfPossibleResult = possibleResult;
std::sort (copyOfPossibleResult.begin (), copyOfPossibleResult.end ());
if (std::adjacent_find (copyOfPossibleResult.begin (), copyOfPossibleResult.end ()) == copyOfPossibleResult.end ())
{
permutations.push_back (possibleResult);
}
});
return permutations;
}
int
main ()
{
auto results = oldSubset (4, { 1, 2, 3, 4, 5, 6});
for(auto const& result:results){
std::copy (result.begin (), result.end (), std::ostream_iterator<int> (std::cout, " "));
std::cout<<std::endl;
}
}
输出
1 2 3 4
1 2 3 5
1 2 3 6
1 2 4 5
1 2 4 6
1 2 5 6
1 3 2 4
1 3 2 5
1 3 2 6
1 3 4 5
1 3 4 6
1 3 5 6
1 4 2 3
1 4 2 5
1 4 2 6
1 4 3 5
1 4 3 6
1 4 5 6
1 5 2 3
1 5 2 4
1 5 2 6
1 5 3 4
1 5 3 6
1 5 4 6
1 6 2 3
1 6 2 4
1 6 2 5
1 6 3 4
1 6 3 5
1 6 4 5
2 3 1 4
2 3 1 5
2 3 1 6
2 3 4 5
2 3 4 6
2 3 5 6
2 4 1 3
2 4 1 5
2 4 1 6
2 4 3 5
2 4 3 6
2 4 5 6
2 5 1 3
2 5 1 4
2 5 1 6
2 5 3 4
2 5 3 6
2 5 4 6
2 6 1 3
2 6 1 4
2 6 1 5
2 6 3 4
2 6 3 5
2 6 4 5
3 4 1 2
3 4 1 5
3 4 1 6
3 4 2 5
3 4 2 6
3 4 5 6
3 5 1 2
3 5 1 4
3 5 1 6
3 5 2 4
3 5 2 6
3 5 4 6
3 6 1 2
3 6 1 4
3 6 1 5
3 6 2 4
3 6 2 5
3 6 4 5
4 5 1 2
4 5 1 3
4 5 1 6
4 5 2 3
4 5 2 6
4 5 3 6
4 6 1 2
4 6 1 3
4 6 1 5
4 6 2 3
4 6 2 5
4 6 3 5
5 6 1 2
5 6 1 3
5 6 1 4
5 6 2 3
5 6 2 4
5 6 3 4
编辑：优化版本
子集
#include <vector>
#include <tuple>
#include <iostream>
#include <numeric>
typedef std::tuple<std::vector<u_int8_t>, std::vector<std::vector<u_int8_t> > > subsetAndCombinations;
// Requires: sequence from begin to end is sorted
// middle is between begin and end
template <typename Bidi, typename Functor>
void
for_each_permuted_combination (Bidi begin, Bidi middle, Bidi end, Functor func)
{
do
{
func (begin, middle);
std::reverse (middle, end);
}
while (std::next_permutation (begin, end));
}
std::vector<std::vector<u_int8_t> >
subsetPermutation (long int subsetSize, std::vector<uint8_t> setOfNumbers)
{
if (subsetSize % 2 != 0) return {};
std::vector<std::vector<u_int8_t> > subsets{};
for_each_permuted_combination (setOfNumbers.begin (), setOfNumbers.begin () + subsetSize / 2, setOfNumbers.end (), [&subsets] (auto begin, auto end) mutable {
if (std::is_sorted (begin, end))
{
subsets.push_back ({ begin, end });
}
});
return subsets;
}
subsetAndCombinations
combinationsFor (std::vector<u_int8_t> const &numbersToCheck, std::vector<std::vector<u_int8_t> > const &subResults, std::vector<u_int8_t> const &numbersToChoseFrom)
{
auto result = std::tuple<std::vector<u_int8_t>, std::vector<std::vector<u_int8_t> > >{};
std::get<0> (result) = numbersToCheck;
std::get<1> (result).reserve (subResults.size ());
std::vector<u_int8_t> numbers (numbersToChoseFrom.size () - numbersToCheck.size ());
std::set_difference (numbersToChoseFrom.begin (), numbersToChoseFrom.end (), numbersToCheck.begin (), numbersToCheck.end (), numbers.begin ());
std::transform (subResults.begin (), subResults.end (), std::back_inserter (std::get<1> (result)), [&numbers] (auto indexes) {
std::transform (indexes.begin (), indexes.end (), indexes.begin (), [&numbers] (auto index) { return numbers[index]; });
return indexes;
});
return result;
}
std::vector<subsetAndCombinations>
subset (long int k, size_t n)
{
auto indexes = std::vector<uint8_t> (n);
std::iota (indexes.begin (), indexes.end (), 0);
auto results = subsetPermutation (k, indexes);
auto subResult = subsetPermutation (k, std::vector<uint8_t> (indexes.begin (), indexes.begin () + static_cast<long int> (n) - (k / 2)));
auto combineResult = std::vector<subsetAndCombinations>{};
for (auto result : results)
{
combineResult.push_back (combinationsFor (result, subResult, indexes));
}
return combineResult;
}
int
main ()
{
auto results = subset (4, 6);
//print results
for (auto const &[subset, combis] : results)
{
for (auto const &combi : combis)
{
std::copy (subset.begin (), subset.end (), std::ostream_iterator<int> (std::cout, " "));
std::copy (combi.begin (), combi.end (), std::ostream_iterator<int> (std::cout, " "));
std::cout << std::endl;
}
std::cout << std::endl;
}
}
edit2：oldSubset 与在 Intel(R) Core(TM) i5-8600K 上使用 catch2 的子集的基准测试 CPU @ 3.60GHz
clang 版本 13.0.0 发布版本
benchmark name samples iterations estimated
mean low mean high mean
std dev low std dev high std dev
-------------------------------------------------------------------------------
subset (4, sixNumbers) 100 8 4.2488 ms
5.12302 us 5.11219 us 5.15303 us
85.5219 ns 37.5917 ns 183.126 ns
oldSubset (4, sixNumbers) 100 1 5.3749 ms
54.1088 us 53.6284 us 55.3097 us
3.60139 us 1.65755 us 7.04574 us
subset (4, eightNumbers) 100 2 4.1362 ms
20.6127 us 20.3747 us 21.221 us
1.80225 us 845.815 ns 3.48066 us
oldSubset (4, eightNumbers) 100 1 24.4414 ms
237.982 us 236.57 us 240.066 us
8.63522 us 6.29346 us 12.1139 us
subset (6, eightNumbers) 100 1 4.107 ms
41.1901 us 41.005 us 41.7309 us
1.48208 us 634.215 ns 3.21124 us
oldSubset (6, eightNumbers) 100 1 149.468 ms
1.49836 ms 1.49526 ms 1.50226 ms
17.5873 us 14.9794 us 22.8566 us
subset (4, tenNumbers) 100 1 6.5134 ms
65.0695 us 64.5343 us 65.9829 us
3.4798 us 2.28411 us 4.82172 us
oldSubset (4, tenNumbers) 100 1 74.4154 ms
754.08 us 752.067 us 756.94 us
12.1161 us 9.50739 us 15.514 us
subset (6, tenNumbers) 100 1 21.2435 ms
209.317 us 207.847 us 211.412 us
8.88665 us 6.72703 us 11.1798 us
oldSubset (6, tenNumbers) 100 1 1.17232 s
11.7905 ms 11.7811 ms 11.8024 ms
53.7095 us 43.4715 us 65.5498 us
subset (8, tenNumbers) 100 1 23.4467 ms
235.972 us 234.262 us 238.712 us
10.8037 us 7.82671 us 16.3172 us
oldSubset (8, tenNumbers) 100 1 6.65554 s
66.7037 ms 66.5035 ms 66.9362 ms
1.09843 ms 954.738 us 1.22926 ms
subset (4, twelveNumbers) 100 1 14.8182 ms
149.715 us 148.325 us 152.211 us
9.22947 us 5.93872 us 14.6366 us
oldSubset (4, twelveNumbers) 100 1 204.43 ms
2.06251 ms 2.05898 ms 2.06644 ms
18.9013 us 14.9089 us 25.4169 us
subset (6, twelveNumbers) 100 1 85.5855 ms
841.024 us 837.534 us 845.313 us
19.7371 us 16.5515 us 24.1813 us
oldSubset (6, twelveNumbers) 100 1 6.65107 s
67.0061 ms 66.9113 ms 67.1053 ms
495.839 us 452.768 us 552.615 us
subset (8, twelveNumbers) 100 1 176.525 ms
1.76037 ms 1.75612 ms 1.76481 ms
22.2971 us 20.032 us 25.2517 us
oldSubset (8, twelveNumbers) 100 1 1.36774 m
819.4 ms 817.476 ms 821.68 ms
10.7189 ms 9.24014 ms 12.3794 ms
subset (10, twelveNumbers) 100 1 196.563 ms
1.94786 ms 1.93109 ms 1.96496 ms
86.618 us 77.6169 us 96.7013 us
oldSubset (10, twelveNumbers) 100 1 6.28968 m
3.83712 s 3.83005 s 3.84504 s
38.1357 ms 33.2592 ms 44.7012 ms
g++ (GCC) 11.1.0 发布版本
benchmark name samples iterations estimated
mean low mean high mean
std dev low std dev high std dev
-------------------------------------------------------------------------------
subset (4, sixNumbers) 100 5 2.2055 ms
4.39944 us 4.38703 us 4.44751 us
106.292 ns 11.2639 ns 244.087 ns
oldSubset (4, sixNumbers) 100 1 5.2325 ms
51.7199 us 51.6355 us 51.9248 us
628.408 ns 315.255 ns 1.25787 us
subset (4, eightNumbers) 100 2 3.473 ms
17.2042 us 17.0591 us 17.8612 us
1.3454 us 169.46 ns 3.18688 us
oldSubset (4, eightNumbers) 100 1 24.246 ms
243.944 us 243.561 us 244.451 us
2.23092 us 1.79177 us 2.77771 us
subset (6, eightNumbers) 100 1 3.6771 ms
37.6169 us 37.4309 us 38.1215 us
1.44523 us 666.679 ns 3.09803 us
oldSubset (6, eightNumbers) 100 1 145.011 ms
1.40323 ms 1.40017 ms 1.40992 ms
22.0044 us 11.2033 us 39.7721 us
subset (4, tenNumbers) 100 1 5.7933 ms
58.8654 us 58.6273 us 59.5799 us
1.9226 us 788.588 ns 4.18631 us
oldSubset (4, tenNumbers) 100 1 79.7406 ms
793.094 us 792.263 us 794.172 us
4.80223 us 3.88654 us 5.93634 us
subset (6, tenNumbers) 100 1 18.3623 ms
188.659 us 188.158 us 190.088 us
3.97281 us 1.77668 us 8.57928 us
oldSubset (6, tenNumbers) 100 1 1.16914 s
11.6407 ms 11.6321 ms 11.6509 ms
47.6677 us 39.6378 us 60.7322 us
subset (8, tenNumbers) 100 1 22.1842 ms
222.242 us 221.612 us 223.478 us
4.32973 us 2.0686 us 8.21289 us
oldSubset (8, tenNumbers) 100 1 6.398 s
63.9016 ms 63.8632 ms 63.9403 ms
196.147 us 177.473 us 221.609 us
subset (4, twelveNumbers) 100 1 12.2964 ms
124.878 us 124.642 us 125.304 us
1.57641 us 1.02773 us 2.91879 us
oldSubset (4, twelveNumbers) 100 1 219.962 ms
2.18378 ms 2.1825 ms 2.18628 ms
8.76462 us 5.40766 us 16.4105 us
subset (6, twelveNumbers) 100 1 74.5191 ms
749.617 us 748.214 us 753.058 us
10.4827 us 5.42864 us 21.6588 us
oldSubset (6, twelveNumbers) 100 1 6.53912 s
65.2901 ms 65.2766 ms 65.3227 ms
100.232 us 50.7812 us 201.115 us
subset (8, twelveNumbers) 100 1 157.06 ms
1.58509 ms 1.58038 ms 1.59278 ms
30.1286 us 21.3724 us 49.5146 us
oldSubset (8, twelveNumbers) 100 1 1.30347 m
775.358 ms 773.562 ms 776.915 ms
8.46007 ms 7.32211 ms 9.60251 ms
subset (10, twelveNumbers) 100 1 189.041 ms
1.89293 ms 1.88865 ms 1.90194 ms
30.2312 us 15.9272 us 58.5911 us
oldSubset (10, twelveNumbers) 100 1 5.27331 m
3.14281 s 3.13666 s 3.14754 s
27.4681 ms 22.0504 ms 33.0537 ms
这是 Python 中的解决方案 - 抱歉，没有时间用 C++ 编写它。 foo 生成器计算纸牌总数和发给玩家的纸牌总和，假设每个玩家收到的纸牌数量相同。然后它会在每次迭代时生成下一个组合。
del_elmts 和 restore_elmts 函数只是为了避免在从牌组中移除玩家 1 的手时将整个数组 P 复制到临时数组中。警告：Python 仍然通过 [:n-k//2] 范围访问生成几乎完整的副本，但在 C++ 中，您可以通过使组合函数更智能一些来避免这种情况。
import itertools
def del_elmts(li,delset):
for i in range(len(delset)-1,-1,-1):
if (delset[i] < len(li)-len(delset)):
li[delset[i]] = li[len(li)-len(delset)+i]
def restore_elmts(li,delset):
for i in delset:
li[i] = i
def foo(n,k):
if k % 2 != 0: raise ValueError
P = list(range(n))
for p in itertools.combinations(P,k//2):
del_elmts(P,p)
for p2 in itertools.combinations(P[:n-k//2],k//2):
yield p+p2
restore_elmts(P,p)
x = foo(6,4)
for y in x:
print(list(map(lambda x: x+1,y)))
PS: 如果你想将它与另一个算法进行比较，你可能需要对输出的前半部分和后半部分进行排序。