Finding Permutations of Strings with no Repeats [duplicate]

Question

I have posted this question already on this forum here, but seeing as no one has answered I decided to try here.

Basically, I'm looking for a way to permute an array of integers given a range with no repeated permutations. I've had trouble understanding how to find permutations in the past, so I was hoping someone could give me an in-depth explaination of what I need to implement and why.

Here is my code as of now :

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define LENGTH 2 double NumberOfPermuationsOfString( int length, char minimum, char maximum ) { return pow( ( maximum - minimum ) + 1, length ); } int NextPermutation( char * buffer, char minimum, char maximum ) { const size_t length = strlen( buffer ) + 1; int i = 0; for ( ; i < length; ++i ) { /* I don't know what to do here... */ } return 0; } void DisplayPermutations( int length, char minimum, char maximum ) { char buffer[( length + 1 )]; memset( buffer, 0, sizeof( buffer ) ); memset( buffer, minimum, sizeof( buffer ) - 1 ); int i = 0; do { printf( "%s\n", buffer ); } while ( NextPermutation( &buffer[0], minimum, maximum ) ); } int main( ) { printf( "Iterating through %0.lf permuations...\n", NumberOfPermuationsOfString( LENGTH, 'a', 'z' ) ); DisplayPermutations( LENGTH, 'a', 'z' ); return 0; }

THIS ISN'T C#, DON'T LET THE NAMING CONVENTION FOOL YOU...

What do you mean by "no repeated permutations" ? Do you intend to treat 1,2,3 and 3,2,1 the same ? — Mohan
– Mohan, Commented Apr 17, 2014 at 23:20
I don't want to have "abc" once, and then appear again later. Also how is this a duplicate? This isn't C#... — user3476738
– user3476738, Commented Apr 17, 2014 at 23:40

Craig Gidney · Accepted Answer · 2014-04-17 23:19:52Z

Eric Lippert, author of the Fabulous Adventures in Coding blog, has a good series on Producing Permutations.

Amongst the explaining, he provides code. For example, the following snippet from part four does what you want and allows random access (but uses a custom type):

public static Permutation NthPermutation(int size, BigInteger index) { if (index < 0 || index >= Factorial(size)) throw new ArgumentOutOfRangeException("index"); if (size == 0) // index must be zero since it is smaller than 0! return Empty; BigInteger group = index / size; // What block are we in? Permutation permutation = NthPermutation(size - 1, group); bool forwards = group % 2 != 0; // Forwards or backwards? int insert = (int) (index % size); // Where are we making the insert? return new Permutation( permutation.InsertAt(forwards ? insert : size - insert - 1, size - 1)); }

I'm not doing this in C#... Which means I don't have access to methods like that.
You should be able to extract the underlying logic and translate it to C++.

Collectives™ on Stack Overflow

Finding Permutations of Strings with no Repeats [duplicate]

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related