Print all increasing sequences of length k from first n natural numbers - GeeksforGeeks
Given two positive integers n and k, print all increasing sequences of length k such that the elements in every sequence are from first n natural numbers.
The idea is to create an array of length k. The array stores current sequence. For every position in array, we check the previous element and one by one put all elements greater than the previous element. If there is no previous element (first position), we put all numbers from 1 to n.
These 2 solutions uses stack or list, set value, and reset(remove) it. It's better we just set(len,value).
http://ideone.com/142pes
http://ideone.com/pJUWFl
Todo: iterative version:
http://ideone.com/yhaSB7
Read full article from Print all increasing sequences of length k from first n natural numbers - GeeksforGeeks
Given two positive integers n and k, print all increasing sequences of length k such that the elements in every sequence are from first n natural numbers.
The idea is to create an array of length k. The array stores current sequence. For every position in array, we check the previous element and one by one put all elements greater than the previous element. If there is no previous element (first position), we put all numbers from 1 to n.
// A recursive function to print all increasing sequences
// of first n natural numbers. Every sequence should be
// length k. The array arr[] is used to store current
// sequence.
void
printSeqUtil(
int
n,
int
k,
int
&len,
int
arr[])
{
// If length of current increasing sequence becomes k,
// print it
if
(len == k)
{
printArr(arr, k);
return
;
}
// Decide the starting number to put at current position:
// If length is 0, then there are no previous elements
// in arr[]. So start putting new numbers with 1.
// If length is not 0, then start from value of
// previous element plus 1.
int
i = (len == 0)? 1 : arr[len-1] + 1;
// Increase length
len++;
// Put all numbers (which are greater than the previous
// element) at new position.
while
(i<=n)
{
arr[len-1] = i;
printSeqUtil(n, k, len, arr);
i++;
}
// This is important. The variable 'len' is shared among
// all function calls in recursion tree. Its value must be
// brought back before next iteration of while loop
len--;
}
// This function prints all increasing sequences of
// first n natural numbers. The length of every sequence
// must be k. This function mainly uses printSeqUtil()
void
printSeq(
int
n,
int
k)
{
int
arr[k];
// An array to store individual sequences
int
len = 0;
// Initial length of current sequence
printSeqUtil(n, k, len, arr);
}
These 2 solutions uses stack or list, set value, and reset(remove) it. It's better we just set(len,value).
http://ideone.com/142pes
http://ideone.com/pJUWFl
Todo: iterative version:
http://ideone.com/yhaSB7
Read full article from Print all increasing sequences of length k from first n natural numbers - GeeksforGeeks