Is recursion or stack necessary for factorial time complexity algorithms?

0
votes

I have a set with elements. I need to generate all the permutations of those elements.

The time complexity of the algorithm that I'm using is O(n!) and it is recursion based. Naturally every recursive algorithm can be converted to non-recursive using an infinite loop and a stack.

Is it possible to generate all the permutations without using either recursion or the stack + loop equivalence ?

2
algorithmrecursionbig-otime-complexity
The answer to "Is recursion or stack necessary for factorial time complexity algorithms" in general is no. Take for example a code that simply iterates through all numbers from 1 to n!. As for "Is it possible to generate all the permutations without using either recursion or the stack + loop equivalence ?" you can find the answer here. - Rufflewind
@Rufflewind This could be an answer, not a comment :) - Adam Stelmaszczyk
@AdamStelmaszczyk: I was but I felt the question may be considered duplicate to the one I already linked. - Rufflewind
@Rufflewind It's still fine to post an answer to such question. In this case, I think this is not a duplicate, the question here is not the same as "How to efficiently generate all possible permutations of a linked list?". - Adam Stelmaszczyk

2 Answers

1
votes

The answer to

Is recursion or stack necessary for factorial time complexity algorithms

in general is no, trivially. Take for example a code that simply iterates through all numbers from 1 to n!:

for i from 1 to factorial(n):
    play("ni.mp3")

As for

Is it possible to generate all the permutations without using either recursion or the stack + loop equivalence ?

the answer is yes and you can find the answer here. There are several different vraiations available depending on the order that you'd like them to be generated. Here's an example from the first answer:

You start from the rightmost number and go one position to the left until you see a number that is smaller than its neighbour. Than you place there the number that is next in value, and order all the remaining numbers in increasing order after it. Do this until there is nothing more to do. Put a little thought in it and you can order the numbers in linear time with respect to their number.

1
votes

As answerd before:
No, recursion and stack are not necessary for factorial time complexity algorithms.

But as I read your post, it looks like you want to ask instead

Is it possible to generate all permutations of n elements faster than O(n!)?

The answer to that is also: no.

Since there are n! different permutations of n elements, every algorithm that saves or displays or does anything with all n! permutations, requires at least O(n!) time. This includes generation of the permutations.