-3

Please understand that this is not a duplicate question. This question needs sorted combinations. Please read the question before. The combination can have repeats of a number. Currently, i have tried generating permutations of n-k+1 0s and k 1s. But it does not produce the combinations with repeats. For example: Choosing 3 numbers from 0, 1,....n, it generates 9 combinations:

(0 1 2), (0 1 3), (0 1 4), (0 2 3), (0 3 4), (1 2 3), (1 2 4), (1 3 4), (2 3 4)

I need it include these combinations too:

(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4), (0, 1, 1), (0, 2, 2), (0, 3, 3), (0, 4, 4), (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 3, 3), (1, 4, 4), (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 3), (2, 4, 4), (3, 3, 3), (3, 3, 4), (3, 4, 4), (4, 4, 4)

What's the most efficient way to get this result? I have used next_permutation to generate the combination right now. Take a look please:

 vector<ll> nums, tmp; for(i = 0; i <= m - n; i++) { nums.push_back(0); } for(i = 0; i < n; i++) { nums.push_back(1); } do { tmp.clear(); for(i = 0; i <= m; i++) { if(nums[i] == 1) { tmp.push_back(i); } } for(i = 0; i < tmp.size(); i++) { cout << tmp[i] << " "; } cout << endl; } while(next_permutation(nums.begin(), nums.end()));
Improve this question
8
  • 1
    `std::next_permutation' Commented Jun 8, 2015 at 9:51
  • 1
    The naive solution? Three nested loops. Commented Jun 8, 2015 at 9:53
  • It would be helpful to understand why you need this result, and what you have achieved so far. Even more so if it's course homework, because you're less likely to learn from a non-homework answer. Commented Jun 8, 2015 at 9:56
  • 2
    BTW, you do realise that combinations and permutation contradict each other? Commented Jun 8, 2015 at 9:56
  • @TobySpeight I do realize it. This is not homework. Commented Jun 8, 2015 at 11:00

2 Answers 2

Reset to default
2

Your 'combinations' are essentially k-digit numbers in base-N numeral system. There are N^k such numbers.

The simplest method to generate them is recursive.

You can also organize simple for-cycle in range 0..N^k-1 and represent cycle counter in the mentioned system. Pseudocode

for (i=0; i<N^k; i++) { //N^k is Power, not xor t = i d = 0 digit = {0} while t > 0 do { digit[d++] = t%N //modulus t = t / N //integer division } output digit array }
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

Following may help:

bool increment(std::vector<int>& v, int maxSize) { for (auto it = v.rbegin(); it != v.rend(); ++it) { ++*it; if (*it != maxSize) { return true; } *it = 0; } return false; }

Usage:

std::vector<int> v(3); do { // Do stuff with v } while (increment(v, 10));

Live demo

Improve this answer

1 Comment

Each combination needs to be sorted.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.