Finding Permutations of Strings with no Repeats

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, Apr 17 '14 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, Apr 17 '14 at 23:40

score 0 · Answer 1 · answered Apr 17 '14 at 23:19

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. — user3476738, Apr 17 '14 at 23:41
You should be able to extract the underlying logic and translate it to C++. — Craig Gidney, Apr 18 '14 at 16:32

Finding Permutations of Strings with no Repeats

1 Answers1