c++ - C ++初心者のニーズは、整数の組み合わせを印刷するのに役立ちます

Question

私が与えられたとしましょう：

1. 整数の範囲iRange（つまり、1からiRange）および
2. 希望する数の組み合わせ

考えられるすべての組み合わせの数を見つけて、これらすべての組み合わせを印刷したいと思います。

例えば：

与えられた：iRange = 5とn = 3

その場合、組み合わせの数はiRange! / ((iRange!-n!)*n!) = 5! / (5-3)! * 3! = 10組み合わせであり、出力は次のとおりです。

123 - 124 - 125 - 134 - 135 - 145 - 234 - 235 - 245 - 345

もう一つの例：

与えられた：iRange = 4とn = 2

その場合、組み合わせの数はiRange! / ((iRange!-n!)*n!) = 4! / (4-2)! * 2! = 6組み合わせであり、出力は次のとおりです。

12 - 13 - 14 - 23 - 24 - 34

これまでの私の試みは次のとおりです。

#include <iostream>
using namespace std;

int iRange= 0;
int iN=0;

int fact(int n)
{
    if ( n<1)
        return 1;
    else
    return fact(n-1)*n;
}

void print_combinations(int n, int iMxM)
{
    int iBigSetFact=fact(iMxM);
    int iDiffFact=fact(iMxM-n);
    int iSmallSetFact=fact(n);
    int iNoTotComb = (iBigSetFact/(iDiffFact*iSmallSetFact));
    cout<<"The number of possible combinations is: "<<iNoTotComb<<endl;
    cout<<" and these combinations are the following: "<<endl;


    int i, j, k;
    for (i = 0; i < iMxM - 1; i++)
    {
        for (j = i + 1; j < iMxM ; j++)
        {
            //for (k = j + 1; k < iMxM; k++)
                cout<<i+1<<j+1<<endl;
        }
    }
}

int main()
{
    cout<<"Please give the range (max) within which the combinations are to be found: "<<endl;
    cin>>iRange;
    cout<<"Please give the desired number of combinations: "<<endl; 
    cin>>iN;
    print_combinations(iN,iRange);
    return 0;   
}

私の問題： 組み合わせの印刷に関連する私のコードの部分は、に対してのみ機能し、一般的にn = 2, iRange = 4は機能させることができません。niRange

Answer 1

ソリューションはn=2でのみ機能します。n intの配列（コーム）を使用することを考えてください。そうすると、ループは配列の最後の項目をチェックします。そのアイテムが最大更新に達したら、comb [n-2]アイテムを作成し、最後のアイテムを前の値+1に設定します。

基本的には時計のように機能しますが、アップティックするものと次の最小値を見つけるためのロジックが必要です。

Answer 2

再帰の良い問題のように見えます。

[ 、 ]の範囲f(prefix, iMin, iMax, n)の数字のすべての組み合わせを出力し、組み合わせの総数を返す関数を定義します。= 1の場合、からまでのすべての桁を出力し、を返す必要があります。niMiniMaxniMiniMaxiMax - iMin + 1

あなたiRange = 5とn = 3ケースについては、あなたはf("", 1, 5, 3)。出力はである必要があります123 - 124 - 125 - 134 - 135 - 145 - 234 - 235 - 245 - 345。

出力の最初のグループは、の出力の前に単に1接頭辞が付けられていることに注意してください。f("", 2, 5, 2)つまりf("1", 2, 5, 2)、その後にf("2", 3, 5, 2)とが続きf("3", 4, 5, 2)ます。ループでそれを行う方法をご覧ください。この間、n上記の= 1の場合、および不正な入力のトラップ（何も出力せず、0を返す場合に最適です。ループが単純化されるはずです）、を書き込むことができるはずですf()。

これは宿題のように見えるので、私は足を止めています。これで始められますか？

編集：ちょっとした笑いのために、私はPythonバージョンを書きました。Pythonは、物事のセットやリストを投げ回して読みやすくするのが簡単です。

#!/usr/bin/env python

def Combos(items, n):
    if n <= 0 or len(items) == 0:
        return []
    if n == 1:
        return [[x] for x in items]
    result = []
    for k in range(len(items) - n + 1):
        for s in Combos(items[k+1:], n - 1):
            result.append([items[k]] + s)
    return result

comb = Combos([str(x) for x in range(1, 6)], 3)
print len(comb), " - ".join(["".join(c) for c in comb])

Combos()リスト内のアイテムのタイプは関係ないことに注意してくださいitems。

Answer 3

これは単純な再帰的ソリューションの例です。再帰をサイクルに置き換えると、より最適な実装が存在すると思います。それはあなたの宿題かもしれません:)

#include <stdio.h>

const int iRange = 9;
const int n = 4;


// A more efficient way to calculate binomial coefficient, in my opinion
int Cnm(int n, int m)
{
    int i;
    int result = 1;

    for (i = m + 1; i <= n; ++i)
        result *= i;

    for (i = n - m; i > 1; --i)
        result /= i;

    return result;
}


print_digits(int *digits)
{
    int i;
    for (i = 0; i < n; ++i) {
        printf("%d", digits[i]);
    }
    printf("\n");
}

void plus_one(int *digits, int index)
{
    int i;

    // Increment current digit
    ++digits[index];

    // If it is the leftmost digit, run to the right, setup all the others
    if (index == 0) {
        for (i = 1; i < n; ++i)
            digits[i] = digits[i-1] + 1;
    }
    // step back by one digit recursively
    else if (digits[index] > iRange) {
        plus_one(digits, index - 1);
    }
    // otherwise run to the right, setting up other digits, and break the recursion once a digit exceeds iRange
    else {
        for (i = index + 1; i < n; ++i) {
            digits[i] = digits[i-1] + 1;

            if (digits[i] > iRange) {
                plus_one(digits, i - 1);
                break;
            }
        }
    }
}

int main()
{
    int i;
    int digits[n];

    for (i = 0; i < n; ++i) {
        digits[i] = i + 1;
    }

    printf("%d\n\n", Cnm(iRange, n));

    // *** This loop has been updated ***
    while (digits[0] <= iRange - n + 1) {
        print_digits(digits);
        plus_one(digits, n - 1);
    }

    return 0;
}

Answer 4

再帰的な解決策で編集されたコードは次のとおりです：D：D ：

#include <iostream>

int iRange=0;   
int iN=0;           //Number of items taken from iRange, for which u want to print out the combinations
int iTotalCombs=0;
int* pTheRange;
int* pTempRange;

int find_factorial(int n)
{
    if ( n<1)
        return 1;
    else
    return find_factorial(n-1)*n;
}

//--->Here is another solution:
void print_out_combinations(int *P, int K, int n_i) 
{
    if (K == 0)
    {
        for (int j =iN;j>0;j--)
        std::cout<<P[j]<<" ";
        std::cout<<std::endl;
    }
    else
        for (int i = n_i; i < iRange; i++) 
        {
            P[K] = pTheRange[i];
            print_out_combinations(P, K-1, i+1);
        }
}
//Here ends the solution...

int main() 
{
    std::cout<<"Give the set of items -iRange- = ";
    std::cin>>iRange;
    std::cout<<"Give the items # -iN- of iRange for which the combinations will be created = ";
    std::cin>>iN;

    pTheRange = new int[iRange];
    for (int i = 0;i<iRange;i++)
    {
        pTheRange[i]=i+1;
    }
    pTempRange = new int[iN];

    iTotalCombs = (find_factorial(iRange)/(find_factorial(iRange-iN)*find_factorial(iN)));

    std::cout<<"The number of possible combinations is: "<<iTotalCombs<<std::endl;
    std::cout<<"i.e.the combinations of "<<iN<<" elements drawn from a set of size "<<iRange<<" are: "<<std::endl;
    print_out_combinations(pTempRange, iN, 0);
    return 0;
}

Answer 5

これは、（sts :: setに基づく）異なるインターフェイスを備えた私のC ++関数ですが、同じタスクを実行します。

typedef std::set<int> NumbersSet;
typedef std::set<NumbersSet> CombinationsSet;

CombinationsSet MakeCombinations(const NumbersSet& numbers, int count)
{
  CombinationsSet result;

  if (!count) throw std::exception();

  if (count == numbers.size())
  {
    result.insert(NumbersSet(numbers.begin(), numbers.end()));
    return result;
  }

  // combinations with 1 element
  if (!(count - 1) || (numbers.size() <= 1))
  {
    for (auto number = numbers.begin(); number != numbers.end(); ++number)
    {
      NumbersSet single_combination;
      single_combination.insert(*number);
      result.insert(single_combination);
    }
    return result;
  }

  // Combinations with (count - 1) without current number
  int first_num = *numbers.begin();
  NumbersSet truncated_numbers = numbers;
  truncated_numbers.erase(first_num);
  CombinationsSet subcombinations = MakeCombinations(truncated_numbers, count - 1);

  for (auto subcombination = subcombinations.begin(); subcombination != subcombinations.end(); ++subcombination)
  {
    NumbersSet cmb = *subcombination;
    // Add current number
    cmb.insert(first_num);
    result.insert(cmb);
  }

  // Combinations with (count) without current number
  subcombinations = MakeCombinations(truncated_numbers, count);
  result.insert(subcombinations.begin(), subcombinations.end());

  return result;
}

Answer 6

next_combination()に似た関数を作成しましたが、機能next_permutation()させるには有効な入力が必要です

//nums should always be in ascending order

    vector <int> next_combination(vector<int>nums, int max){
    int size = nums.size();
    
    if(nums[size-1]+1<=max){
        nums[size-1]++;
        return nums;
    }else{
        if(nums[0] == max - (size -1)){
            nums[0] = -1;
            return nums; 
        }
        
        int pos;
        int negate = -1;
        for(int i = size-2; i>=0; i--){
            if(nums[i]+1 <= max + negate){
                pos = i;
                break;
            }
            negate --;
        }
        nums[pos]++;
        pos++;
        while(pos<size){
            nums[pos] = nums[pos-1]+1;
            pos++;
        }
    }
    return nums;
}