Print all sequences of given length | GeeksforGeeks
Given two integers k and n, write a function that prints all the sequences of length k composed of numbers 1,2..n. You need to print these sequences in sorted order.
Method 2 (Tricky and Recursive)
The idea is to use one more parameter index. The function printSequencesRecur keeps all the terms in arr[] sane till index, update the value at index and recursively calls itself for more terms after index.
we can avoid use of arrays for small sequences that can fit in an integer. ==> Ask interviewer, the range of the number, whether it can fit in integer or long, what's the output: integer or list of int or string(in this case, better to use list)?
Read full article from Print all sequences of given length | GeeksforGeeks
Given two integers k and n, write a function that prints all the sequences of length k composed of numbers 1,2..n. You need to print these sequences in sorted order.
Method 2 (Tricky and Recursive)
The idea is to use one more parameter index. The function printSequencesRecur keeps all the terms in arr[] sane till index, update the value at index and recursively calls itself for more terms after index.
void printSequencesRecur(int arr[], int n, int k, int index){ int i; if (k == 0) { printArray(arr, index); } if (k > 0) { for(i = 1; i<=n; ++i) { arr[index] = i; printSequencesRecur(arr, n, k-1, index+1); } }}void printSequences(int n, int k){ int *arr = new int[k]; printSequencesRecur(arr, n, k, 0); delete(arr); // free dynamically allocated array return;}void printSeqRecur(int num, int pos, int k, int n){ if (pos == k) { printf("%d \n", num); return; } for (int i = 1; i <= n; i++) { printSeqRecur(num * 10 + i, pos + 1, k, n); }}void printSequences(int k, int n){ printSeqRecur(0, 0, k, n);}
Method 1 (Simple and Iterative):
Time Complexity: There are total n^k sequences. Printing a sequence and finding its successor take O(k) time. So time complexity of above implementation is O(k*n^k).
1) Create an output array arr[] of size k. Initialize the array as {1, 1…1}.
2) Print the array arr[].
3) Update the array arr[] so that it becomes immediate successor (to be printed) of itself. For example, immediate successor of {1, 1, 1} is {1, 1, 2}, immediate successor of {1, 4, 4} is {2, 1, 1} and immediate successor of {4, 4, 3} is {4 4 4}.
4) Repeat steps 2 and 3 while there is a successor array. In other words, while the output array arr[] doesn’t become {n, n .. n}
3) Update the array arr[] so that it becomes immediate successor (to be printed) of itself. For example, immediate successor of {1, 1, 1} is {1, 1, 2}, immediate successor of {1, 4, 4} is {2, 1, 1} and immediate successor of {4, 4, 3} is {4 4 4}.
4) Repeat steps 2 and 3 while there is a successor array. In other words, while the output array arr[] doesn’t become {n, n .. n}
1) Start from the rightmost term arr[k-1] and move toward left. Find the first element arr[p] that is not same as n.
2) Increment arr[p] by 1
3) Starting from arr[p+1] to arr[k-1], set the value of all terms as 1.
2) Increment arr[p] by 1
3) Starting from arr[p+1] to arr[k-1], set the value of all terms as 1.
/* This function returns 0 if there are no more sequences to be printed, otherwise modifies arr[] so that arr[] contains next sequence to be printed */int getSuccessor(int arr[], int k, int n){ /* start from the rightmost side and find the first number less than n */ int p = k - 1; while (arr[p] == n) p--; /* If all numbers are n in the array then there is no successor, return 0 */ if (p < 0) return 0; /* Update arr[] so that it contains successor */ arr[p] = arr[p] + 1; for(int i = p + 1; i < k; i++) arr[i] = 1; return 1;}void printSequences(int n, int k){ int *arr = new int[k]; /* Initialize the current sequence as the first sequence to be printed */ for(int i = 0; i < k; i++) arr[i] = 1; /* The loop breaks when there are no more successors to be printed */ while(1) { /* Print the current sequence */ printArray(arr, k); /* Update arr[] so that it contains next sequence to be printed. And if there are no more sequences then break the loop */ if(getSuccessor(arr, k, n) == 0) break; } delete(arr); // free dynamically allocated array return;}