implement combinatoric algorithm in c++("put apples in different plates") -

i generated group of n-element arrays consist of alternating 1 , -1 followed zeros, starting 1.

for example, n=5, arrays are: 10000, 1-1000, 1-1100, 1-11-10, 1-11-11,

i need “insert” zeros between non-zero numbers each array: 1-1100 in above example, enumeration is:

1 -1 1 0 0,(allow 1 , -1 have no 0 between them.)

1 -1 0 1 0,

1 0 -1 1 0,

1 0 -1 0 1,

1 0 0 -1 1,

1 -1 0 0 1 (the first element still needs 1)

is there algorithm generate such enumeration given array above format?

i think problem putting identical apples different plates(because putting zeros different gaps gives different enumeration) , allowing plates remain empty.

i need print out possibilities, not count them. can't figure out way it.

this simpler appears.

the first element 1. thus, can ignore that, , prepend 1 our answers.

the nonzero elements, after initial 1, -1, 1, -1, etc. since pattern fixed, can replace nonzeros 1, translate back.

so have list of 0's , 1's , need generate permutations.

putting in python:

#!/usr/bin/env python3  n = 5  def main():     # k = number of nonzeros, minus initial 1 that's there     k in range(n):         seq = [0] * (n - 1 - k) + [1] * k         p in next_permutation(seq):             result = decorate(p)             print(" ".join("{:2d}".format(i) in result))  # adapted http://stackoverflow.com/questions/4250125 def next_permutation(seq):     seq = seq[:]     first = 0     last = len(seq)     yield seq      if last == 1:         raise stopiteration      while true:         next = last - 1         while true:             next1 = next             next -= 1             if seq[next] < seq[next1]:                 mid = last - 1                 while seq[next] >= seq[mid]:                     mid -= 1                 seq[next], seq[mid] = seq[mid], seq[next]                 seq = seq[:next1] + list(reversed(seq[next1:last])) + seq[last:]                 yield seq[:]                 break             if next == first:                 raise stopiteration     raise stopiteration  def decorate(seq):     # convert 1's alternating -1, 1, prepend 1 whole thing     seq = seq[:]     n = -1     in range(len(seq)):         if seq[i]:             seq[i] = n             n = -n     return [1] + seq  main()