### Problem

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.### Examples

Example 1Input: k = 2, n = 3 Output: 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3

Example 2

Input: k = 3, n = 4 Output: 1 1 1 1 1 2 1 1 3 1 1 4 1 2 1 ..... ..... 4 3 4 4 4 1 4 4 2 4 4 3 4 4 4

###
Solution** **

**Method 1 - Simple and Iterative**

The simple idea to print all sequences in sorted order is to start from {1 1 … 1} and keep incrementing the sequence while the sequence doesn’t become {n n … n}. Following is the detailed process.

- Create an output array arr[] of size k. Initialize the array as {1, 1…1}.
- Print the array arr[].
- 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}.
- 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}

To find the immediate successor, we find the point p in the previously printed array. To find point p, we start from rightmost side and keep moving till we find a number arr[p] such that arr[p] is smaller than n (or not n). Once we find such a point, we increment it arr[p] by 1 and make all the elements after arr[p] as 1 i.e., we do arr[p+1] = 1, arr[p+2] = 1 .. arr[k-1] = 1. Following are the detailed steps to get immediate successor of arr[]

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.

// 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; } // The main function that prints all sequences from 1, 1, ..1 to n, n, ..n 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; } return; }

*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).

**Method 2 (Tricky and Recursive)**

The recursive function

*printSequencesRecur*generates and prints all sequences of length k. 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.

// The core function that recursively generates and prints all sequences of // length k 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); } } } // A function that uses printSequencesRecur() to prints all sequences // from 1, 1, ..1 to n, n, ..n void printSequences(int n, int k) { int[] arr = new int[k]; printSequencesRecur(arr, n, k, 0); return; }

*Time Complexity:*There are n^k sequences and printing a sequence takes O(k) time. So time complexity is O(k*n^k).

**References**

## 0 comments:

## Post a Comment