使用c ++的排列和组合 [英] Permutations &/ Combinations using c++

查看：57 发布时间：2020/5/6 11:10:42 c++ algorithm math combinations permutation

本文介绍了使用c ++的排列和组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我的代码需要其他版本的排列.我可以实现我想要的功能，但是它不够通用.我的算法随着我的要求不断扩大.但这不应该.

I need a different version of permutations for my code. I could able to achieve what I want but it is not generic enough. my algorithm keeps going bigger along with my requirements. But that should not be.

这不是任何人的家庭作业，对于我的关键项目，我需要它，想知道boost或其他任何可用的预定义算法.

This is not a home work for any one, I need it for one my critical projects, wondering if any pre-defined algorithms available from boost or any other.

以下是使用c ++的next_permutation的标准版本.

Below is the standard version of next_permutation using c++.

// next_permutation example
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation

int main () 
{
  int myints[] = {1,2,3};
  do 
  {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while ( std::next_permutation(myints,myints+3) );


  return 0;
}

给出以下输出:

但是我的要求是:-假设我有1到9个数字: 1,2,3,4,5,6,7,8,9

But my requirement is :- Let's say I have 1 to 9 numbers : 1,2,3,4,5,6,7,8,9

我需要可变长度的排列，并且只能以升序排列，并且没有重复.

And I need a variable length of permutations and in only ASCENDING order and with out DUPLICATES.

假设我需要3位数的排列长度，然后需要输出如下.

Let's say i need 3 digit length of permutations then i need output as below.

123
124
125
.
.
.
128
129
134   // After 129 next one should be exactly 134
135      // ascending order mandatory
136
.
.
.
148
149
156   // exactly 156 after 149, ascending order mandatory
.
.
.
489   // exactly 567 after 489, because after 3rd digit 9, 2nd digit
567   // will be increased to 49? , so there is no possibility for
.     // 3rd digit, so first digit gets incremented to 5 then 6 then
.     // 7, in ascending order.
.     
.
.
789   // and this should be the last set I need.

我的列表最多可以包含数百个数字，并且可变长度可以是1到最大列表的大小.

My list may contain upto couple of hundred's of numbers and variable length can be 1 to up to Size of the list.

我自己的算法适用于特定的变量长度和特定的大小，当它们都改变时，我需要编写大量代码.因此，正在寻找通用的.

My own algorithm is working for specific variable length, and a specific size, when they both changes, i need to write huge code. so, looking for a generic one.

我什至不确定是否将其称为置换"或这种数学/逻辑有不同的名称.

I am not even sure if this is called as Permutations or there is a different name available for this kind of math/logic.

先谢谢了. 麝香的

推荐答案

可以使用简单的迭代算法完成此任务.只需递增第一个可以递增的元素，然后在其之前重新缩放元素，直到没有要递增的元素为止.

This task can be done with a simple iterative algorithm. Just increment the first element that can be incremented and rescale the elements before it until there is no element to be incremented.

int a[] = {0,1,2,3,4,5,6,7,8,9}; // elements: must be ascending in this case
int n = sizeof(a)/sizeof(int);
int digits = 7; // number of elements you want to choose
vector<int> indexes; // creating the first combination
for ( int i=digits-1;i>=0;--i ){
    indexes.push_back(i);
}

while (1){
    /// printing the current combination
    for ( int i=indexes.size()-1;i>=0;--i ){
        cout << a[indexes[i]] ;
    } cout << endl;
    ///
    int i = 0;
    while ( i < indexes.size() && indexes[i] == n-1-i ) // finding the first element
        ++i;                                            // that can be incremented
    if ( i==indexes.size() ) // if no element can be incremented, we are done
        break;
    indexes[i]++; // increment the first element
    for ( int j=0;j<i;++j ){ // rescale elements before it to first combination
        indexes[j] = indexes[i]+(i-j);
    }
}

输出:

这篇关于使用c ++的排列和组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文

使用c ++的排列和组合 [英] Permutations &/ Combinations using c++

问题描述

推荐答案

相关文章

C/C++开发最新文章

热门教程

热门工具

登录关闭

使用c ++的排列和组合 [英] Permutations &amp;/ Combinations using c++

问题描述

推荐答案

相关文章

C/C++开发最新文章

热门教程

热门工具

登录 关闭

使用c ++的排列和组合 [英] Permutations &/ Combinations using c++

登录关闭