vendredi 5 mars 2021

C++ Generator for permutations with a twist (decreasing each position)

I'm no mathematician, so I don't know if there is terminology for this (I could not find it).

What I'm looking for is C++ code to generate all permutations, with repetition, but with a twist: the first position can have n-1 as the highest value, the second can have n-2 as the highest value and so on n-(n...0). E.g. given n=3 with repetition allowed this should result into:

[0,0,0]   ✓
[0,0,1] ✗
[0,0,2] ✗
[0,1,0]   ✓
[0,1,1] ✗
[0,1,2] ✗
[0,2,0]   ✓
[0,2,1] ✗
[0,2,2] ✗
[1,0,0]   ✓
[1,0,1] ✗
[1,0,2] ✗
[1,1,0]   ✓
[1,1,1] ✗
[1,1,2] ✗
[1,2,0]   ✓
[1,2,1] ✗
[1,2,2] ✗
[2,0,0]   ✓
[2,0,1] ✗
[2,0,2] ✗
[2,1,0]   ✓
[2,1,1] ✗
[2,1,2] ✗
[2,2,0]   ✓
[2,2,1] ✗
[2,2,2] ✗

So it's like a N-length list of permutations of N with repetition and except plus the per position limitation . Is there an existing name or description for this kind of sequence?

I can make something like a recursive pattern, but I would like a generator. Solely for speed purposes. Is it likely this will be faster than a function? How would you approach this?

Aucun commentaire:

Enregistrer un commentaire