1
$\begingroup$

Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order?

Thanks.

$\endgroup$
1
$\begingroup$

You might not be able to generate lexicographic permutations for any sequence of arbitrary objects. In order to do so, you will need some way of comparing two objects and determining which one is smaller.

Assuming you have this, you could use the following algorithm to generate all permutations of a sequence of $n$ objects in lexicographic order.

  1. Start by sorting the input sequence, $A$, of $n$ objects
  2. Find the largest index $k$ such that $A[k] < A[k+1]$. If no such $k$ is found, terminate. The sequence $A$ contains the last lexicographic permutation.
  3. Find the largest index $l$ such that $A[k] < A[l]$
  4. Swap $A[k]$ and $A[l]$
  5. Reverse the sub-sequence starting from $A[k+1]$ to the final element, $A[n-1]$

Note that this algorithm generates the next lexicographic permutation of $A$ in-place. To generate all permutations, you can repeat this until no more permutations are found.

$\endgroup$
  • $\begingroup$ How would I compare the complexity of the answer reported here with the answer given in my code below, for iterating through the entire permutation list in lexicographic order? $\endgroup$ – Joselin Jocklingson May 6 at 18:45
  • $\begingroup$ Indeed, a given order on the objects would need to be taken as a given. Alternatively, one can simply assume the lexicographically smaller permutation is the one corresponding to the order you input the objects into your algorithm. $\endgroup$ – Joselin Jocklingson May 6 at 18:46
-2
$\begingroup$

I found the following code here:

https://github.com/nzanella/universitycode/blob/master/lexpermlist.c

The code exploits the idea that the next permutation can be computed from the previous one by group theoretic multiplication by a product of four specifically indexed permutations in each step, which can be discerned from the code.

/* lists all permutations of the first n positive integers */
/* in lexicographic order.                                 */

#include <stdio.h>

#define N 20 /* maximum length of an n-tuple */
#define TRUE 1
#define FALSE 0

typedef int Bool;

int a[N + 1], n;

void step_in(void);
void next_permutation(const int left_index, const int right_index);
void print_permutation(void);
void get_n(void);
void initialize_a(void);

main()
{
   get_n();
   initialize_a();

   step_in();

   return 0;
}

/**********************************************************
 * step_in: this recursive function manipulates the       *
 *          values of left_index, right_index, and        *
 *          direction. These variables control the        *
 *          general flow of the algorithm, determining    *
 *          whether a permutation is to be computed or    *
 *          printed and whether the function is to be     *
 *          exited.                                       *
 **********************************************************/

void step_in(void)
{
   static enum {LEFT, RIGHT} direction = RIGHT;
   static left_index = 0;
   int right_index;   /* successive calls of step_in hide */
                      /* previous values of right_index   */

   for (;;) {
      if (direction == RIGHT) {
         ++left_index;
         right_index = n;
         if (left_index == n - 1) {
            print_permutation();
            next_permutation(left_index, right_index);
            print_permutation();
            direction = LEFT;
            break;
         }
         else if (left_index < n - 1)
            step_in();
         else {
            /* special cases where n equals 0 or 1 are treated here */
            print_permutation();
            break;
         }
      }
      else {
         --left_index;
         if (left_index < right_index) {
            next_permutation(left_index, right_index);
            --right_index;
            direction = RIGHT;
            step_in();
         }
         else
            break;
      }
   }
}

/**********************************************************
 * next_permutation: permutes the elements of the array a *
 *                   amongst themselves to obtain a new   *
 *                   permutation of these elements.       *
 **********************************************************/

void next_permutation(const int left_index, const int right_index)
{
   int i;
   int temp[N + 1];
   int top = left_index;

   temp[top] = a[right_index];
   ++top;

   for (i = n; i > right_index; top++, i--)
      temp[top] = a[i];

   temp[top] = a[left_index];
   ++top;

   for (i = right_index - 1; i > left_index; top++, i--)
      temp[top] = a[i];

   for (i = left_index; i <= n; i++)
      a[i] = temp[i];
}

/**********************************************************
 * print_permutation: prints current permutation.         *
 **********************************************************/

void print_permutation(void)
{
   int i;

   printf("\n(");
   if (n > 0) {
      printf(" %2d", a[1]);
      for (i = 2; i <= n; i++)
         printf(", %2d", a[i]);
   }
   printf(" )\n\n");
}

/**********************************************************
 * get_n: prompt user for permutation length n. Read all  *
 *        characters entered by user up to the newline    * 
 *        character. Repeat if either invalid data or an  *
 *        illegal permutation length is entered.          *
 **********************************************************/

void get_n(void)
{
   Bool invalid_int_val;
   char next_char;

   for (;;) {
      invalid_int_val = FALSE;
      printf("\n");
      printf("Enter n: ");
      scanf("%d", &n);
      for(;;) {
         if ((next_char = getchar()) == '\n')
            break;
         else if (next_char != ' ' && next_char != '\t') {
            invalid_int_val = TRUE;
            for(; getchar() != '\n';)
               ;
            break;
         }
      }
      if (invalid_int_val || n < 0 || n > N) {
         printf("\n");
         printf("The number n must be an integer between %d and %d. Try again.\n", 0, N);
      }
      else
         break;
   }
}

/**********************************************************
 * initialize_a: initializes array a.                     *
 **********************************************************/

void initialize_a(void)
{
   int i;

   for (i = 1; i <= n; i++)
      a[i] = i;
}
$\endgroup$
  • 2
    $\begingroup$ We're not a coding site. We discourage code-only answers. Instead, we're looking for algorithms, ideas, concise pseudocode, explanation, etc. Please edit your question to explain the main ideas of your approach. $\endgroup$ – D.W. Apr 12 at 20:36
  • $\begingroup$ How can I format my code properly though. I will add an explanation. $\endgroup$ – Joselin Jocklingson Apr 16 at 13:13
  • $\begingroup$ I've added some comments above the code. Please remove the downvote $\endgroup$ – Joselin Jocklingson May 6 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.