Print all permutation in lexicographic order

Question

I want to print all permutation of string in lexicographic order. I wrote this code:

void permute(char *a, int i, int n) {
   if (i == (n-1)) printf("\"%s\"\n", a);
   else {
       for (int j = i; j < n; j++) {
           swap((a+i), (a+j));
           permute(a, i+1, n);
           swap((a+i), (a+j));
       }
   }
}

Let's take for example string abc, I want to receive all permutation in lexicographic order as in the left column, but I have result as in the right column.

"abc"                   "abc"
"acb"                   "acb"
"bac"                   "bac"
"bca"                   "bca"
"cab"            <
"cba"                   "cba"
                 >      "cab"

Can someone help me with this? I saw some algorithms, but they look difficult. I think I can save all generated strings in an array and then sort this array, but I cannot write this (I'm a beginner in C).

Answer 1

In C

There's a pretty straightforward description of an algorithm (plus implementation) at geeksforgeeks:

Given a string, print all permutations of it in sorted order. For example, if the input string is “ABC”, then output should be “ABC, ACB, BAC, BCA, CAB, CBA”.

We have discussed a program to print all permutations in this post, but here we must print the permutations in increasing order.

Following are the steps to print the permutations lexicographic-ally

1. Sort the given string in non-decreasing order and print it. The first permutation is always the string sorted in non-decreasing order.

2. Start generating next higher permutation. Do it until next higher permutation is not possible. If we reach a permutation where all characters are sorted in non-increasing order, then that permutation is the last permutation.

Steps to generate the next higher permutation:
1. Take the previously printed permutation and find the rightmost character in it, which is smaller than its next character. Let us call this character as ‘first character’.

2. Now find the ceiling of the ‘first character’. Ceiling is the smallest character on right of ‘first character’, which is greater than ‘first character’. Let us call the ceil character as ‘second character’.

3. Swap the two characters found in above 2 steps.

4. Sort the substring (in non-decreasing order) after the original index of ‘first character’.

I've re-implemented it below:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void swap(char* left, char* right)
{
    char temp = *left;
    *left = *right;
    *right = temp;
}
int compare (const void * a, const void * b)
{
  return ( *(char*)a - *(char*)b );
}
void PrintSortedPermutations(char* inStr)
{
    // Re-implementation of algorithm described here:
    // http://www.geeksforgeeks.org/lexicographic-permutations-of-string/
    int strSize = strlen(inStr);
    // 0. Ensure input container is sorted
    qsort(inStr, strSize, sizeof(char), compare);


    int largerPermFound = 1;
    do{
        // 1. Print next permutation
        printf("%s\n", inStr);
        // 2. Find rightmost char that is smaller than char to its right
        int i;
        for (i = strSize - 2; i >= 0 && inStr[i] >= inStr[i+1]; --i){}

        // if we couldn't find one, we're finished, else we can swap somewhere
        if (i > -1)
        {
            // 3 find character at index j such that 
            // inStr[j] = min(inStr[k]) && inStr[k] > inStr[i] for all k > i
            int j = i+1;
            int k;
            for(k=j;k<strSize && inStr[k];++k)
            {
                if (inStr[k] > inStr[i] && inStr[k] < inStr[j])
                    j = k;
            }

            // 3. Swap chars at i and j
            swap(&inStr[i], &inStr[j]);

            // 4. Sort string to the right of i
            qsort(inStr+i+1, strSize-i-1, sizeof(char), compare);
        }
        else
        {
            largerPermFound = 0;
        }
    }while(largerPermFound);
}

int main(void) {
    char str[] = "abc";

    PrintSortedPermutations(str);
    return 0;
}

Output

abc
acb
bac
bca
cab
cba

Live Demo

---

In C++

std::next_permutation from the <algorithm> library will do this for you, just make sure you sort your container first:

Return value

true if the function could rearrange the object as a lexicographicaly greater permutation. Otherwise, the function returns false to indicate that the arrangement is not greater than the previous, but the lowest possible (sorted in ascending order).

For example:

std::string myStr = "abc";
std::stable_sort(std::begin(myStr), std::end(myStr));
do {
    for(auto&& element : myStr)
        std::cout << element << " ";
    std::cout << std::endl;
} while (std::next_permutation(std::begin(myStr), std::end(myStr)));

Output:

a b c
a c b
b a c
b c a
c a b
c b a

Live Demo

Answer 2

I am presuming you want a recursive version.

Here are two solutions.

Solution 1)

Since you want lexicographic, all you need to do is pick the next smallest possible when you need to pick. That's it!

For example, here is a recursive version in python

def permute(done, remaining):
  if not remaining:
    print done
    return

  sorted_rem = sorted(remaining)
  l = len(sorted_rem)

  for i in xrange(0, l):
    c = sorted_rem[i]

    # Move to c to done portion.
    done.append(c)
    remaining.remove(c)

    # Permute the remaining
    permute(done, remaining)

    # Put c back.
    remaining.append(c)
    # Remove from done.
    del done[-1]

permute([], [1,2,3,4])

That's it.

Solution 2)

While Solution 1 works and is easy to understand, I suspect we might be wasting some time by sorting. This solution is closer to what you have.

Recursion is basically mathematical induction in disguise, and that way of thinking is really useful in understanding how to write recursive programs.

For example, assume your permute method always constructs the permutations in lexicographic order.

Here is a recursive version, with that assumption, please read the comments to understand what is going on.

// By induction assumption, permute(a, i, n)
// goes through all the permutations of a[i], ..., a[n-1]
// in lexicographic order, by modifying a itself.
void permute(char *a, int i, int n) {
    if (i == (n-1)) {
       printf("%s\n", a);
      return;
    }

    int j;
    // We pick the n-i posibilities for the position a+i, then recursively
    // compute the permutations of a[i+1], ..., a[n-1]
    // So first pick the smallest possible for a+i, recurse.
    // Then the next possible for a+i, then recurse etc.

    for (j = i; j < n; j++) {
      permute(a, i+1, n);
      // By our induction assumption, at this point, 
      // a[i+1], a[i+2], .., a[n-1]
      // must be the lexicographically the largest possible!

      // So now reverse that portion.
      reverse(a+i+1, a+n-1);

      // Now we need to pick the lexicographically next element for
      // position a+i. This is nothing but the element which is just
      // larger than the current a+i.

      int k = i+1;
      while(k < n && a[i] > a[k]) {
        k++;
      }

      if (k >= n) {
        continue;
      }
      // Choose the next value for a+i.
      swap(a+i, a+k);
    }
    // Notice that the portion a[i+1], ..., a[n-1]  is sorted increasing.
    // when the loop exits. Also a[i] will be the largest element.
    // We need to reverse so that a[i], .., a[n-1] is the lexicographically
    // largest permutation to  maintain the induction (recursion) assumption.
    reverse(a+i+1, a+n-1);
}

Notice the similarity between this, and the iterative version (specified by the others and section below), where you reverse a chunk at the end, and swap two elements.

---

btw, the common iterative algorithm for generating permutations in lexicographic order is Narayana Pandita's algorithm, mentioned by other, but not by name.

See this link: http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

This is what std::next of C++ and a host of other libraries use.

This algorithm even works when there are repeated elements, and can in fact be used to generate combinations! (Initialize your array with zeroes and ones).

Answer 3

IMHO, it would be simpler to first sort the characters of the string because the number of permutations (n!) is always greater (or equal for n = 1 or 2) than the number of characters.

And you were not far from the solution but you must rotate instead of swap. Here is a slight variation that returns an array of dynamically allocated strings that are printed in the main :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int char_compare(const void *a, const void *b) {
    return (*((char *) a)) - (*((char *) b));
}

int fact(int n) {
    int f = 1;
    while (n > 0) {
        f *= n--;
        if (f < 0) return 0;
    }
    return f;
}

void rotateback(char *a, int i, int j) {
    int k;
    char tmp;
    tmp = a[i];
    for(k=i; k<j; k++) {
        a[k] = a[k+1];
    }
    a[j] = tmp;
}

void rotate(char *a, int i, int j) {
    int k;
    char tmp;
    tmp = a[j];
    for(k=j; k>i; k--) {
        a[k] = a[k-1];
    }
    a[i] = tmp;
}

void permute(char *a, int i, int n, char ***permuts) {
    int j;
    if (i == (n-1)) {
        **permuts = strdup(a);  // store a copy of the string
        *permuts += 1;          // and point to next location
    }
   else {
       for (j = i; j < n; j++) {
           rotate(a, i, j);
           permute(a, i+1, n, permuts);
           rotateback(a, i, j);
       }
   }
}
char ** permutations(const char *str_orig) {
    int i, j;
    size_t n = strlen(str_orig);
    size_t fact_n = fact(n);
    char ** permuts, **work;

    char * str = strdup(str_orig); // get a local copy
    qsort(str, n, 1, char_compare); // and sort it

    permuts = work = calloc(fact_n, sizeof(char *)); // allocate n! pointers

    permute(str, 0, n, &work);
    return permuts;
}

int main() {
    char str[] = "cab";
    int i;

    char **permuts = permutations(str);

    for (i=0; i<fact(strlen(str)); i++) {
        printf("\"%s\"\n", permuts[i]);
        free(permuts[i]);
    }
    free(permuts);
    return 0;
}

Output is correctly :

"abc"
"acb"
"bac"
"bca"
"cab"
"cba"

Answer 4

Another twist on the lexical string permutations is to store the permutation in a dynamically allocated array of pointers-to-string and pass the array to qsort to provide output in lexical order. Since permutations grow exponentially, checks for memory exhaustion after each allocation are especially important. The string size below is limited to 16 characters, which may still result in memory exhaustion depending on the amount of memory available.

Updated passing the address of the array to hold the string permutations was required for reallocation to work in the recursive function.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXS 128
#define MAXC 16

size_t maxs;

void swap (char *x, char *y);
int cmp_pa (const void * a, const void * b);
char **realloc_char (char **sp, size_t *n);
void permute_pa (char ***pa, size_t *idx, char *a, int i, int n);

int main (int argc, char **argv)
{
    size_t i = 0;
    size_t idx = 0;
    size_t len = 0;
    char a[MAXC] = {0};
    char **pa = NULL;

    maxs = MAXS;                            /* initialize realloc counter   */

    if (argc > 1)                           /* set string to permute        */
        strcpy (a, argv[1]);
    else
        strcpy (a, "abc");

    len = strlen (a);                       /* lenght to permute or MAXC    */
    if (len > MAXC) len = MAXC;

    if (!(pa = calloc (MAXS, sizeof *pa)))  /* allocate MAXS pointers       */
        return 1;

    permute_pa (&pa, &idx, a, 0, len - 1);  /* call permute function        */

    printf ("\n no of permutations : %zu\n\n", idx);
    printf (" unsorted permutations of %s\n\n", a);

    for (i = 0; i < idx; i++)
        printf (" %s\n", pa[i]);

    qsort (pa, idx, sizeof *pa, cmp_pa);    /* sort array of permutations   */

    printf ("\n sorted permutations of %s\n\n", a);

    for (i = 0; i < idx; i++)
        printf (" %s\n", pa[i]);

    for (i = 0; i < idx; i++)               /* free all allocated memory    */
        free (pa[i]);
    free (pa);

    return 0;
}

/* Function to swap values at two pointers */
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

/* qsort compare function */
int cmp_pa (const void * a, const void * b)
{   return strcmp (*(char**)a, *(char**)b); }

/* realloc an array of pointers to strings setting memory to 0. */
char **realloc_char (char **sp, size_t *n)
{
    char **tmp = realloc (sp, 2 * *n * sizeof *sp);
    if (!tmp) {
        fprintf (stderr, "Error: struct reallocation failure.\n");
        // return NULL;
        exit (EXIT_FAILURE);
    }
    sp = tmp;
    memset (sp + *n, 0, *n * sizeof *sp); /* memset new ptrs 0 */
    *n *= 2;

    return sp;
}

/* Function to store permutations of string in array of pointers-to-string
This function takes five parameters:
1. allocated array of pointers-to-string
2. pointer to array index
3. string to permute
4. starting index of the string (zero based)
5. ending index of the string. (zero based)
*/
void permute_pa (char ***pa, size_t *idx, char *a, int i, int n)
{
    int j;
    if (i == n) {
        (*pa)[*idx] = strdup (a);
        if (!(*pa)[*idx]) {
            fprintf (stderr, "%s() error: virtual memory exhausted.\n", __func__);
            exit (EXIT_FAILURE);
        }
        (*idx)++;
        if (*idx == maxs)
            *pa = realloc_char (*pa, &maxs);
    }
    else {
        for (j = i; j <= n; j++) {
            swap ((a+i), (a+j));
            permute_pa (pa, idx, a, i+1, n);
            swap ((a+i), (a+j));
        }
    }
}

Output

$ ./bin/str_permute_lex

 no of permutations : 6

 unsorted permutations of abc

 abc
 acb
 bac
 bca
 cba
 cab

 sorted permutations of abc

 abc
 acb
 bac
 bca
 cab
 cba

Memory Error Check

$ valgrind ./bin/str_permute_lex
==29709== Memcheck, a memory error detector
==29709== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==29709== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==29709== Command: ./bin/str_permute_lex
==29709==

 no of permutations : 6

 <snip>

==29709==
==29709== HEAP SUMMARY:
==29709==     in use at exit: 0 bytes in 0 blocks
==29709==   total heap usage: 7 allocs, 7 frees, 1,048 bytes allocated
==29709==
==29709== All heap blocks were freed -- no leaks are possible
==29709==
==29709== For counts of detected and suppressed errors, rerun with: -v
==29709== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)

Answer 5

The basic idea is to start with our main string as "" and remaining string as "abc" (or any you want).

Now to the main string append character by character. Such a way that it don't repeat the used characters (for all possible characters).

Repeat the same until you get length n ( length of main string ).

Okay, the explanation isn't clear but watch out the code. It will make everything clear.

#include<iostream>

void perm(std::string sub, std::string rem, int n)
{
    if(n==0)
        //print if n is zero i.e length achieved
        std::cout<<sub<<"\n";

    for(int i=0; i<n; i++)
        //append a character and pass remaining to rem string
        perm(sub + rem[i] , rem.substr(0,i) + rem.substr(i+1,n-1), n-1);
}

int main()
{
    perm("", "abc", 3);
}

Output

abc
acb
bac
bca
cab
cba

Answer 6

This is voluntarily an answer that does not answer this question.

This other question was marked as a duplicate to this one. This answer would be acceptable for the other question even if it is non sense here.

This could be a simple recursive C implementation to get all permutations in lexicographic order. It is not optimized but easy to understand and to implement:

• get an array for the elements to permute
• at any step, iterate through the elements that have not been used until here
  • add one of the iterated elements to the array of used elements
  • recurse
• when the array of used element is full print it.

Concrete implementation:

#include <stdio.h>

#define SIZE 4

void disp(int *fullarr, int n, int * begin, int pos) {
    int i, j;
    int found;
    if (pos == n) {
        for(i=0; i< n; i++) {
            printf("%2d", begin[i]);
        }
        printf("\n");
        return;
    }
    for (i=0; i<n; i++) {
        found = 0;
        for (j=0; j<pos; j++) {
            if (fullarr[i] == begin[j]) {
                found = 1;
                break;
            }
        }
        if (! found) {
            begin[pos] = fullarr[i];
            disp(fullarr, n, begin, pos+1);
        }
    }
}

int main() {
    int i;
    int fullarr[SIZE], begin[SIZE];
    for (i=0; i<SIZE; i++) {
        fullarr[i] = i;
    }
    disp(fullarr, SIZE, begin, 0);
    return 0;
}

Answer 7

OK, here is how to do it in any programming language. I will illustrate it with writing down all the permutations of S4 but one can see easily how in generalizes. One needs to know about special permutations called cycles. The cycle (132) is the permutation that sends 1 to 3, 3 to 2 and 2 back to 1. Think of a numbered circle and one rotates the circle. The cycles (321) and (213) represent the same cycle and permutation. A "two cycle" (13) is a transposition, simply interchanging 1 and 3 and leaving all the other members the same. A "one cycle" (2) sends 2 to 2 and leaves everything else the same, i.e., it does nothing to any element. However, I will write one cycles below to make it look "pretty".

With that intro, let us start with the set {[1,2,3,4]}. We act on this set by the following sets of cycles:

The set {(4)}. This does nothing leaving us with

{[1,2,3,4]}.

We act on this set with the pair of cycles, {(3),(43)}. This gives us

{ [1,2,3,4], [1,2,4,3] }, 

a set with two elements. We act on this second set with the cycles: {(2),(32),(432)}. We have

(2) { [1,2,3,4], [1,2,4,3] } = { [1,2,3,4], [1,2,4,3] }
(32) { [1,2,3,4], [1,2,4,3] } = { [1,3,2,4], [1,3,4,2] }
(432) { [1,2,3,4], [1,2,4,3] } = { [1,4,2,3], [1,4,3,2] }

Writing these out, we have a set of 6 tuples:

{ [1,2,3,4], [1,2,4,3], [1,3,2,4], [1,3,4,2 [1,4,2,3], [1,4,3,2] }

Lastly we hit this set with the cycles {(1),(21),(321),(4321)}. This will give us 24 tuples which are the 4x6 = 24 permutations of S4 - all in lexicographic order!

Answer 8

void permute(string str,int index)
{
 if(index ==  str.size())
 {
    cout<<str<<" ";
    return;
 }
 else
 {
    for(int j=index;j<str.size();j++)
    {
        if(str[index] <= str[j]) // swap only in sorted order 
        swap(str[j],str[index]);
        permute(str,index+1);
        if(str[index] <= str[j]) // swap only in sorted order 
        swap(str[j],str[index]);
    }
 }
}
int main()
{
 int t; 
 string str;
    scanf("%d",&t);
    while(t--){
        // scanf("%d",&n);
        cin>>str;
        sort(str.begin(),str.end());
        permute(str,0);
        cout<<endl;

    }
  return 0;
}

Answer 9

from itertools import combinations

S,k = input().split()
for i in list(range(int(k)+1))[1:]:
   


    for e in combinations(sorted(S),i ):
        print(''.join(e))