logo标签列表

在幂集中，用于组合或子集的下一个排列

c++permutationcombinationspowerset
7

是否有相应的库或函数可以给我一组值的下一个组合，就像next_permutation在C++中为我所做的那样？

1
你需要更加具体明确。 - anon
1
可能更具体一些会更好。 - sblom
可能是https://dev59.com/MnE95IYBdhLWcg3wp_yn的重复问题。 - Potatoswatter
6个回答
10
组合：从马克·纳尔逊在同一主题上的文章中，我们有下一个组合http://marknelson.us/2002/03/01/next-permutation 排列：从STL中，我们有std::next_permutation
 template <typename Iterator>
 inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
 {
    if ((first == last) || (first == k) || (last == k))
       return false;
    Iterator itr1 = first;
    Iterator itr2 = last;
    ++itr1;
    if (last == itr1)
       return false;
    itr1 = last;
    --itr1;
    itr1 = k;
    --itr2;
    while (first != itr1)
    {
       if (*--itr1 < *itr2)
       {
          Iterator j = k;
          while (!(*itr1 < *j)) ++j;
          std::iter_swap(itr1,j);
          ++itr1;
          ++j;
          itr2 = k;
          std::rotate(itr1,j,last);
          while (last != j)
          {
             ++j;
             ++itr2;
          }
          std::rotate(k,itr2,last);
          return true;
       }
    }
    std::rotate(first,k,last);
    return false;
 }
1
我发现很难相信那个算法，因为它的变量命名糟糕透顶，明显还有死代码等问题。 - sehe
我仍然不确定正确性，但至少这里有一个稍微更清晰的版本 https://paste.ubuntu.com/p/yXgtdjTyfD/ - sehe
懒人网络回应说，这个实现看起来要重型得多。https://howardhinnant.github.io/combinations.html /cc @howard-hinnant - sehe
链接已经损坏。 - liorko
8

我不知道有没有相关的工具。基本思路是将元素表示成位数组。例如，你有集合S：

S = {a, b, c}
[i, j, k] // a is the first bit, b is the second bit, c is the third bit

为了生成S的幂集（只需通过简单的加法生成大小为3位的所有数字）：
000 // {}
001 // {c}
010 // {b}
011 // {b, c}
100 // {a}
101 // {a, c}
110 // {a, b}
111 // {a, b, c}

你需要做的就是找到哪些位被设置，并将其与你的集合元素相关联。

最后注意一点，当你想要使用所有元素时，有一种组合可以产生，那就是集合本身，因为在组合中顺序并不重要，所以我们肯定在谈论元素数n，其中0 <= n <= size(S)。

1
真的非常喜欢这个想法！ - bobber205
@bobber205，您能解释一下您遇到的问题吗？ - Khaled Alshaya
@bobber：这里的概念是幂集，与通常所谓的“组合”不同。请搜索该术语。同时参考https://dev59.com/2kzSa4cB1Zd3GeqPpcIs。 - Potatoswatter
@Potatoswatter 如果我错了，请纠正我。集合的子集只是该集合与n个元素中的r个元素的组合。基本上，幂集表示为：S是一个具有n个元素的集合，那么P(s)就是：C(n, 0) + C(n, 1) + C(n, 2) +...+ C(n, r) +...+ C(n, n)。 - Khaled Alshaya
C(n,k)是组合数。∑k=0..n = 2^n是著名的帕斯卡三角恒等式。也许因为函数C需要参数k，有些人倾向于假设组合问题基于特定数量的元素进行选择。 - Potatoswatter
显示剩余4条评论
1

幂集的枚举（即所有大小的组合）可以使用二进制增量算法的改编。

template< class I, class O > // I forward, O bidirectional iterator
O next_subset( I uni_first, I uni_last, // set universe in a range
    O sub_first, O sub_last ) { // current subset in a range
    std::pair< O, I > mis = std::mismatch( sub_first, sub_last, uni_first );
    if ( mis.second == uni_last ) return sub_first; // finished cycle

    O ret;
    if ( mis.first == sub_first ) { // copy elements following mismatch
        std::copy_backward( mis.first, sub_last, ++ (ret = sub_last) ); 
    } else ret = std::copy( mis.first, sub_last, ++ O(sub_first) ); 
    * sub_first = * mis.second; // add first element not yet in result
    return ret; // return end of new subset. (Output range must accommodate.)
}

需要双向迭代器的要求很不幸，但可以通过解决方法来解决。

我本来想让它处理相同的元素（multisets），但是我需要去睡觉了 :v( .

用法：

#include <iostream>
#include <vector>
using namespace std;

char const *fruits_a[] = { "apples", "beans", "cherries", "durian" };
vector< string > fruits( fruits_a, fruits_a + sizeof fruits_a/sizeof *fruits_a );

int main() {
    vector< string > sub_fruits( fruits.size() );
    vector< string >::iterator last_fruit = sub_fruits.begin();

    while ( 
        ( last_fruit = next_subset( fruits.begin(), fruits.end(),
                     sub_fruits.begin(), last_fruit ) )
            != sub_fruits.begin() ) {
        cerr << "size " << last_fruit - sub_fruits.begin() << ": ";
        for ( vector<string>::iterator fit = sub_fruits.begin(); fit != last_fruit; ++ fit ) {
            cerr << * fit << " ";
        }
        cerr << endl;
    }
}

编辑：这是适用于多重集合的版本。集合不必排序，但相同元素必须分组在一起。

#include <iterator>
#include <algorithm>
#include <functional>

template< class I, class O > // I forward, O bidirectional iterator
I next_subset( I uni_first, I uni_last, // set universe in a range
    O sub_first, O sub_last ) { // current subset in a range
    std::pair< O, I > mis = std::mismatch( sub_first, sub_last, uni_first );
    if ( mis.second == uni_last ) return sub_first; // finished cycle

    typedef std::reverse_iterator<O> RO;
    mis.first = std::find_if( RO(mis.first), RO(sub_first), std::bind1st(
        std::not_equal_to< typename std::iterator_traits<O>::value_type >(),
        * mis.second ) ).base(); // move mis.first before identical grouping

    O ret;
    if ( mis.first != sub_first ) { // copy elements after mismatch
        ret = std::copy( mis.first, sub_last, ++ O(sub_first) );
    } else std::copy_backward( mis.first, sub_last, ++ (ret = sub_last) );

    * sub_first = * mis.second; // add first element not yet in result
    return ret;
}

#include <vector>
#include <iostream>
using namespace std;

char const *fruits_a[] = { "apples", "apples", "beans", "beans", "cherries" };
vector< string > fruits( fruits_a, fruits_a + sizeof fruits_a/sizeof *fruits_a );

int main() {
    vector< string > sub_fruits( fruits.size() );
    vector< string >::iterator last_fruit = sub_fruits.begin();

    while (
        ( last_fruit = next_subset( fruits.begin(), fruits.end(),
                                    sub_fruits.begin(), last_fruit )
        ) != sub_fruits.begin() ) {
        cerr << "size " << last_fruit - sub_fruits.begin() << ": ";
        for ( vector<string>::iterator fit = sub_fruits.begin(); fit != last_fruit; ++ fit ) {
            cerr << * fit << " ";
        }
        cerr << endl;
    }
}

输出：

size 1: apples 
size 2: apples apples 
size 1: beans 
size 2: apples beans 
size 3: apples apples beans 
size 2: beans beans 
size 3: apples beans beans 
size 4: apples apples beans beans 
size 1: cherries 
size 2: apples cherries 
size 3: apples apples cherries 
size 2: beans cherries 
size 3: apples beans cherries 
size 4: apples apples beans cherries 
size 3: beans beans cherries 
size 4: apples beans beans cherries 
size 5: apples apples beans beans cherries
1

每当我需要做这个时，我都会使用这个库。它的接口非常类似于 std::next_permutation，所以如果您以前使用过它，那么使用这个库会很容易。

这似乎不是一个真正的 Boost 库... - Potatoswatter
不，但它是有效的，并且在Boost软件许可下获得授权，所以只需将头文件与您的源代码一起使用... - Greg Rogers
0

搜索C++ "next_combination"，找到了this。

  • 从“mid”开始向后搜索，直到找到一个比*(end-1)小的元素。这是我们应该递增的元素。称其为"head_pos"。
  • 从“end”开始向后搜索，直到找到最后一个仍然大于*head_pos的元素。将其称为"tail_pos"。
  • 交换head_pos和tail_pos。以递增顺序重新排列[head_pos + 1, mid[和[tail_pos + 1, end[中的元素。
@bobber：你能说得更具体一点吗？ - Potatoswatter
0

如果您别无选择，只能实现自己的函数，也许这个恐怖可以在那个问题的答案中帮助一点或者其他的恐怖。

从n个元素中返回k个元素的所有组合的算法

我写了一段时间，现在完整的图片已经逃离了我的脑海 :), 但基本思想是这样的：您有原始集合，当前组合是所选元素的迭代器向量。要获取下一个组合，您需要从右到左扫描集合，寻找“气泡”。所谓“气泡”是指一个或多个相邻的未选择元素。该“气泡”可能就在右边。然后，在您的组合中，您将左侧“气泡”的第一个元素与来自集合中位于其右侧的所有其他元素交换，并使用从“气泡”的开头开始的相邻元素子集替换组合中的所有其他元素。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接