CODEWITHSUNDEEP
c++calgorithm
Aks
Aks

Reputation: 5236

Improving the time complexity of all permutations of a given string

The problem is generally posed as given a string, print all permutations of it. For eg, the permutations of string ABC are ABC, ACB, BAC, BCA, CAB, CBA.

The standard solution is a recursive one, given below.

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

This, runs into O(n*n!). Is this the best we can do or is there someway to make this faster?

Upvotes: 2

Views: 901

Answers (4)

Jarod42
Jarod42

Reputation: 217135

std::next_permutation does the job:

#include <algorithm>
#include <iostream>

int main () {
    char s[] = "BAC";

    // let's begin with the lowest lexicographically string.
    std::sort(std::begin(s), std::end(s) - 1); // '- 1' : ignore '\0'
    do {
        std::cout << s << std::endl;
    } while (std::next_permutation(std::begin(s), std::end(s) - 1));
  return 0;
}

Upvotes: 0

son of the northern darkness
son of the northern darkness

Reputation: 709

You can use std::next_permutation. Please, notice it works correctly only on sorted array.
Good points about this solution: 1) It is standard 2) It is non-recursive

Here is an example (http://www.cplusplus.com/reference/algorithm/next_permutation/):

// next_permutation example
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

int main () {
  int myints[] = {1, 2, 3};

  std::sort (myints, myints + 3);

  std::cout << "The 3! possible permutations with 3 elements:\n";
  do {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while (std::next_permutation (myints, myints + 3));

  std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';

  return 0;
}

Upvotes: 2

Łukasz Kidziński
Łukasz Kidziński

Reputation: 1623

Suppose you have n elements and you are looking for kth permutation 0 <= k <= n-1.

  • Create a list elements with all elements and an empty list result
  • while elements not empty:
    • Set p = k % elements.size and k = k / elements.size
    • Remove elements[p] and append it to result

We visit each element from elements only once so it's O(n).

Upvotes: 0

Stefano Falasca
Stefano Falasca

Reputation: 9097

The very result you are looking for contains n*n elements, so this is the best you can get!

Upvotes: 0

Related Questions