Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- void getAllComb(int item, int &r, vector<int> &boxes, int lastItemPosition, int &count){
- //base case
- if(item > r){
- count++;
- for(int i : boxes){
- cout << i;
- }
- cout << '\n';
- return;
- }
- /*
- Follow the same algorithm for generating permutations, Iterate from the index just after where the last item was placed instead of iterating from 0 everytime. This would prevent permuations
- n = 5, r = 3, item = 1
- item 1 has 5 options as all the box are empty, generating sequences such as
- 1 _ _ _ _ , _ 1 _ _ _ , _ _ 1 _ _ , _ _ _ 1 _ , _ _ _ _ 1
- In permuations, the sequence 1 _ _ _ _ & _ 1 _ _ _ would generate permuations as,
- Following the path for sequence 1 _ _ _ _ , at level of item 2, we would generate
- 1 2 _ _ _
- &
- Following the path for sequence _ 1 _ _ _ , at level of item 2, we would generate
- 2 1 _ _ _
- which if you would see carefully, both the sequences are permuations of each other, as 1 & 2 arranged themseleves in 2 boxes = _ _ => 1 2 & 2 1 OR 2! OR [2 P 2]
- NOTE-
- For generating combinations, we need to avoid generating the permutations, and to avoid it we simply keep track of the box which the item at previous level chose.
- So for sequence: 1 _ _ _ _ , at level of item 2, lastItemPosition = 0, we can only choose from index lastItemPosition + 1 to generate 1 2 _ _ _ , 1 _ 2 _ _ , 1 _ _ 2 _ , 1 _ _ _ 2
- Following sequence 1 _ 2 _ _ at level of item 3, lastItemPositionIndex = 2, So we can only choose the box at index 3 & 4 to place the item 3 to generate sequence
- 1 _ 2 3 _ , 1 _ 2 _ 3
- INTUTION on why this works?????
- We are maintaining a singular order of 1 -> 2 -> 3 ... permutations gets generated ONLY when the order of elements is being changed, i.e. elements are being ARRANGED (essentially what we call permuting items). To generate combinations we need to avoid generating sequences such 123, 132, 213, 312, 231, 321, here the order is being changed.
- Permutuation = Ways to arrange items
- Combinations = Ways to choose
- n P r = n! / (n - r)! = Total ways of arranging r items in n boxes. (Order Dependent)
- n C r = n! / (n - r)! r! = Total ways of choosing r boxes for r items. (Order Independent)
- For Permutuation items should be distinct: 1 2 3, r g b balls
- For Combinations items are same/similar (that's why arranging them won't work): i i i , r r r balls
- */
- for(int i = lastItemPosition + 1; i < boxes.size(); i++){
- if(boxes[i] == 0){
- boxes[i] = item;
- getAllComb(item + 1, r, boxes, i, count);
- boxes[i] = 0;
- }
- }
- }
- int main() {
- // your code goes here
- int n, r;
- cin >> n >> r;
- vector<int> boxes(n, 0);
- int count = 0;
- getAllComb(1, r, boxes, -1, count);
- cout << count << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
