يحتاج N ++ Newbie يساعد في طباعة مجموعات من الأعداد الصحيحة

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 وأنا لا أستطيع أن أجعلها تعمل بشكل عام، أي لأي n و iRange.

Answer 1

هنا يتم تحرير التعليمات البرمجية الخاصة بك: 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 2

الحل الخاص بك سوف يعمل فقط من أجل n = 2. فكر في استخدام صفيف (أمشاط) مع N Ints، ثم سيقوم الحلقة بوضع علامة على العنصر الأخير في الصفيف. عندما يصل هذا العنصر إلى ماكس التحديث، ثم تمشيط عنصر [N-2] وقم بتعيين العنصر الأخير إلى القيمة السابقة +1.

تعمل بشكل أساسي على مدار الساعة ولكنك تحتاج إلى منطق للعثور على ما يجب رفعه وما هو الحد الأدنى للقيمة التالية.

Answer 3

يبدو وكأنه مشكلة جيدة للحصول على العودية.

تحديد وظيفة f(prefix, iMin, iMax, n), ، يطبع جميع مجموعات n أرقام في النطاق [iMin, iMax] وإرجاع العدد الإجمالي للمجموعات. بالنسبة n = 1، يجب طباعة كل رقم من iMin ل iMax والعودة iMax - 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().

أتوقف عن ذلك لأن هذا يشبه مهمة الواجبات المنزلية. هل هذا يكفي لتبدأ؟

تحرير: فقط للضحكات، كتبت نسخة بيثون. بيونثون لديه وقت أسهل رمي حول مجموعات وقوائم الأشياء والبقاء مقروءا.

#!/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 4

إليك مثال على حل متكرر عادي. أعتقد أن هناك في التنفيذ الأكثر أهمية إذا استبدلت العودية مع دورات. يمكن أن يكون واجبك منزلك :)

#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 5

هذه هي وظيفة C ++ الخاصة بي مع واجهة مختلفة (بناء على STS :: Set) ولكن أداء نفس المهمة:

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;
}