Strange list - how to start?

[fx11]

My program should read in the value of n
and generate a list the following way:

1<=a1<=a2<=...<=an

AND

ai<=i, i€{1,...,n}, n€Z+ (n is a positive integer)


For example in case of n=3
the list should look like this

1. 1,1,1
2. 1,1,2
3. 1,1,3
4. 1,2,2
5. 1,2,3


As you can see 1,2,2 is the element of the list

but 1,3,3 is not an element because at the second position
only such an element can stand that is less or equal to 2.
a2<=2 (a2==1 or a2==2)



Any idea how to start writing it?

[Peter87]

Is it the algorithm or C++ that you have problem with?

[fx11]

I have made a sketch.
I see how the process works
but I can't compose such an algorithm
from which I could write a c++ code.

[andywestken]

Are you going to have a go at proposing an algorithm?

From your list you can see

1 is followed by 1, 2

and

1,1 is followed by 1, 2, 3
1,2 is followed by 2, 3

A solution for the cases N=2 and N=3 should be (is!) relatively straightforward. Then you could have a go coding that. After which you can generalise it for any N, which is a bit (rather?) more involved.

Andy

[agnophilo]

It's not clear what you're after. Perhaps you could copy your assignment verbatim rather than in your own words?

[giblit]

Try next_permutation or generate algorithms there was a thread like this yesterday

[fx11]

@agnophilo:


I try to explain the task:

input (N): 4
(That means we have four columns for the digits.)
(One column can have digits from 1 to 4.)

output list (without conditions):

1,1,1,1
1,1,1,2
1,1,1,3
1,1,1,4

1,1,2,1
1,1,2,2
1,1,2,3
1,1,2,4

1,1,3,1
1,1,3,2
1,1,3,3
1,1,3,4

...

4,4,4,3
4,4,4,4



BUT there are also other conditions which I have to follow:

1. condition

first column can have only one digit: 1
second column can have only two digits: 1 or 2
third column can have only three digits: 1,2 or 3
fourth column can have only four digits: 1,2,3 or 4
and so on

1,1,1,1
1,1,1,2
1,1,1,3
1,1,1,4

1,1,2,1
1,1,2,2
1,1,2,3
1,1,2,4

1,1,3,1
1,1,3,2
1,1,3,3
1,1,3,4

1,2,1,1
1,2,1,2
1,2,1,3
1,2,1,4

1,2,2,1
1,2,2,2
1,2,2,3
1,2,2,4

1,2,3,1
1,2,3,2
1,2,3,3
1,2,3,4


2. condition:
previous element <= current element <= next element (looking only at one line)

So when both condition fulfilled we get this list (if input was N=4):


1,1,1,1
1,1,1,2
1,1,1,3
1,1,1,4

1,1,2,1 <-- bad (1<=1<=2>1) (not element of this list)
1,1,2,2 <-- right (1<=1<=2<=2)
1,1,2,3 <-- right (1<=1<=2<=3)
1,1,2,4 <-- right (1<=1<=2<=4)

1,1,3,3
1,1,3,4

1,2,2,2
1,2,2,3
1,2,2,4

1,2,3,3
1,2,3,4

[giblit]

http://www.cplusplus.com/forum/beginner/102375/
http://www.cplusplus.com/reference/algorithm/next_permutation/

[andywestken]

I would focus on the starting and termination conditions for each member of the sequence.

I coded the N=2 (with a single for-loop and one cout) and the N=3 case (with two for for-loops and one cout) easily enough. The N=4, 5, 6, ... can be seen to follow. The only "trick" is working out when to start and stop each loop!

And at first glance, I would say that iteration will be required to implement the general case cleanly (all iterative solution can be converted to loops, but not always in a friendly way...)

Andy

[JLBorges]

include <iostream>
#include <vector>

void generate( std::vector<int>& seq, std::size_t pos = 0 )
{
   if( pos == seq.size() ) // pos is beyond the last element; print the seq
   {
       for( int v : seq ) std::cout << v << ' ' ;
       std::cout << '\n' ;
   }
   else // generate sequence starting at pos
   {
       for( std::size_t i = 0 ; i <= pos ; ++i )
       {
           seq[pos] = i+1 ; // place 1,2,3 ... pos+1 at position pos
           generate( seq, pos+1 ) ; // and generate the rest of sequence from pos+1
       }
   }
}

int main()
{
    const std::size_t N = 4 ;
    std::vector<int> seq(N) ;
    generate(seq) ;
}

http://ideone.com/0ryR85

This takes care of just the first condition.

Now, modify this to incorporate the second condition:
previous element <= current element <= next element
Hint: You would need to add an extra parameter to the generate function.

[fx11]

@giblit

I have tried the next_permutation

but there are no repeated elements.

e.g. 1 1 1 1 or 2 2 1 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

// next_permutation example #include <iostream> // std::cout #include <algorithm> // std::next_permutation, std::sort int main () { unsigned int N; std::cout<<"N:"; std::cin>> N; unsigned int * myints = new unsigned int [N]; for(int i=0;i<N;i++) myints[i]=i+1; std::sort (myints,myints+N); do { for(int i=0;i<N;i++){ //conditions goes here std::cout << myints[i] << ' '; } std::cout << std::endl; } while ( std::next_permutation(myints,myints+N) ); return 0; }

N:4 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 Process returned 0 (0x0) execution time : 3.461 s Press any key to continue.

@JLBorges
I will try your solution tomorrow ...
thanks

[andywestken]

Hint: You would need to add an extra parameter to the generate function.

@JLBorges

Actually, your code can (also) be fixed without an additional parameter.

Andy

[JLBorges]

> andywestken
> Actually, your code can (also) be fixed without an additional parameter.

+1

Yes, that information can be computed: pos==0 ? 1 : seq[pos-1]