C ++ Новичок нуждается в помощи для печати комбинаций целых чисел

Предположим, что мне дают:

  1. Диапазон целых чисел iRange (т.е. от 1 до iRange ) и
  2. Требуемое количество комбинаций

Я хочу найти количество всех возможных комбинаций и распечатать все эти комбинации.

Например:

Дано : iRange = 5 и n = 3

Тогда количество комбинаций iRange! / ((iRange!-n!)*n!) = 5! / (5-3)! * 3! = 10 iRange! / ((iRange!-n!)*n!) = 5! / (5-3)! * 3! = 10 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 iRange! / ((iRange!-n!)*n!) = 4! / (4-2)! * 2! = 6 iRange! / ((iRange!-n!)*n!) = 4! / (4-2)! * 2! = 6 комбинаций, а выход:

 12 - 13 - 14 - 23 - 24 - 34 

Моя попытка:

 #include  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: "<>iRange; cout<<"Please give the desired number of combinations: "<>iN; print_combinations(iN,iRange); return 0; } 

Моя проблема: часть моего кода, связанная с печатью комбинаций, работает только для n = 2, iRange = 4 и я не могу заставить ее работать вообще, т. iRange Для любых n и iRange .

Вот ваш код, отредактированный: D: D с рекурсивным решением:

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

Ваше решение будет работать только при n = 2. Подумайте об использовании массива (гребенки) с n ints, затем цикл отметит последний элемент массива. Когда этот элемент достигнет максимального обновления, расчешите элемент [n-2] и установите последний элемент в предыдущее значение +1.

В основном работает как часы, но вам нужна логика, чтобы найти, что нужно всплывать, и какое следующее минимальное значение.

Похож на хорошую проблему для рекурсии.

Определите функцию 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() .

Я останавливаюсь, потому что это выглядит как домашнее задание. Достаточно ли этого, чтобы вы начали?

EDIT: Только для хихиканья, я написал версию Python. Python имеет более легкое время, бросая вокруг наборов и списков вещей и оставаясь parsingчивым.

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

Вот пример простого рекурсивного решения. Я считаю, что существует более оптимальная реализация, если вы замените рекурсию на циклы. Это может быть ваша домашняя работа 🙂

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

Это моя C ++-функция с другим интерфейсом (на основе sts :: set), но выполняющая ту же задачу:

 typedef std::set NumbersSet; typedef std::set 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; }