当前位置: 首页 > 知识库问答 >
问题:

n个不同数的组合

许展鹏
2023-03-14
1 2
3 1
2 4
3 2
 1 2
 | 
 3 1
  \
 2 4
   |
 3 2
 1 2
   | 
 3 1
   |
 2 4
  /
 3 2

我的问题是我无法思考如何编码,因为n<=50和a,b<=16,所以我不确定有多少个不同的数字,如果有16个数字,那么我必须找到16个数字的所有可能的组合,所以指导我通过这个。

共有1个答案

华萧迟
2023-03-14

要形成一个不同数字的列表,只需使用一个“唯一集”,并不断地将所有数字插入其中。在C++中,std::set by definition只存储唯一的数字。

为了找到不同序列的组合数量,您必须保留一个“候选列表”列表,如果他们已经没有这些数字,则继续在其中插入数字,否则删除特定的候选列表。

C++中的完整代码:

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

int main() {

    int n = 4;
    set<int> uniqueNumbers; // ordered set of unique numbers
    vector< set<int> > possibleLists( 1 );
    set<int>::iterator it;

    for ( int i = 0; i < n; i++ ) {

        int num1;
        int num2;
        cin >> num1 >> num2;

        // numbers will be inserted if not already present in set (by definition)
        uniqueNumbers.insert( num1 );
        uniqueNumbers.insert( num2 );

        // make a copy for a possible new branch
        vector< set<int> > possibleListsCopy( possibleLists );

        //int size1 = possibleLists.size();

        for ( int j = 0; j < possibleLists.size(); j++ ) {

            it = possibleLists[j].find( num1 );
            if ( it == possibleLists[j].end() ) {
                possibleLists[j].insert( num1 ); // insert if not found
                //cout << "inserted1 "<<endl;
            }
            else {
                // erase this possible combination
                possibleLists[j].clear();
                possibleLists.erase( possibleLists.begin() + j );
                j--;
            }

        }

        //int size2 = possibleListsCopy.size();

        for ( int j = 0; j < possibleListsCopy.size(); j++ ) {
;

            it = possibleListsCopy[j].find( num2 );
            if ( it == possibleListsCopy[j].end() ) {
                possibleListsCopy[j].insert( num2 ); // insert if not found
            }
            else {
                // erase this possible combination
                possibleListsCopy[j].clear();
                possibleListsCopy.erase( possibleListsCopy.begin() + j );
                j--;
            }

        }

        // concatenate both set of lists.
        possibleLists.insert( possibleLists.end(),
                                possibleListsCopy.begin(),
                                possibleListsCopy.end() );


    }


    cout << " The unique list: ";
    //output the unique list.
    for ( it = uniqueNumbers.begin(); it != uniqueNumbers.end(); it++ )
        cout << *it << " ";

    /*cout << endl << endl;

    cout << "Possible Lists:" << endl;

    for ( int i = 0; i < possibleLists.size(); i++ ) {

        for ( it = possibleLists[i].begin(); it != possibleLists[i].end(); it++ )
            cout << *it << " ";
        cout << endl;

    }*/

    cout << endl << "Total number of combinations: "
        << possibleLists.size() << endl;

    return 0;
}
 类似资料:
  • 底价为125.5元的产品,如何生成10条不低于底价且每条报价高于底价不能超过底价的(100分之一到200分之一间的数)并且10条报价不能相同(报价要相对自然,不是每一个多固定数的那种)的python代码

  • 问题内容: 想象一下,我有一个这样的JS数组: 我想要的是将该数组拆分为N个较小的数组。例如: 对于Python,我有这个: 对于JS,我可以提出的最佳解决方案是递归函数,但我不喜欢它,因为它既复杂又丑陋。这个内部函数返回一个像这样的数组[1,2,3,null,4,5,6,null,7,8],然后我必须再次循环并手动拆分它。(我的第一次尝试是返回此:[1、2、3,[4、5、6,[7、8、9]]],

  • 问题内容: 我正在使用一个查询,查询的一部分获得某一列的前3名。 它创建该列的唯一子查询,并限制3行,然后将这些行过滤到主查询中以进行前3个查询。 所以原始表是这样的: 并且查询返回列的前3名(而不是前3行,仅是): 我正在尝试了解是否有更正确的方法来执行此操作,因为实际查询很大,并且用看起来几乎相同的子查询来复制它的大小,只是为了获得前三名很难并且难以理解/修改。 在Oracle中,是否有更好的

  • 问题内容: 我想在数组中的每个索引处创建一个大小相同的数组。用Java做到这一点的最佳方法是什么? 例如,如果为5且值为boolean ,则数组应为: 问题答案: 您可以尝试以下方法: 手动数组填充的第二种方法:

  • 问题内容: 做到这一点的最佳方法是什么? 问题答案: 使用 array_slice() 这是PHP手册中的一个示例:array_slice 只有一个小问题 如果数组索引对您有意义,请记住这将重置并重新排列 数字 数组索引。您需要设置标志来避免这种情况。(第4个参数,自5.0.2起可用)。 例: 输出:

  • 问题内容: 在JavaScript中,我想不出代码来从n个数组(其中m个元素)中生成组合的代码。对于其他语言,我也曾见过类似的问题,但答案包含了我不确定如何翻译的语法或库魔术。 考虑以下数据: 3个数组,其中包含不同数量的元素。我想做的是通过组合每个数组中的一项来获得所有组合。 例如: 等等。 如果数组的数目是固定的,则很容易进行硬编码实现。但是数组的数量可能会有所不同: 任何帮助将非常感激。 问