Creating Subline Memory Substitutions

Question

I am wondering if there is a simple enough algorithm for generating permutations of N elements, for example 1..N , which uses memory less than O(N) . He does not need to calculate the nth permutation, but it should be able to calculate all the permutations.

Of course, this algorithm must be some kind of generator or use some internal data structure that uses less than O(N) memory, since returning the result as a vector of size N already violates the restriction on sub-linear memory.

Answer 1

Suppose a random permutation is generated one record at a time. The state of the generator must encode the remaining set of elements (execute it before completion), and therefore, since it is impossible to exclude the possibility, the state of the generator is at least n bits.

Answer 2

I think the answer should be no.

Consider a generator for N-element permutations as a finite automaton: it must contain at least as many states as there are permutations, otherwise it will start repeating before it finishes generating all of them.

There is N! such permutations that require at least the ceil (log2 (N!)) bit to represent. Stirling's approximation says that log2 (N!) Is O (N log N), so we cannot create such a generator with sublinear memory.

Answer 3

The C ++ next_permutation performs a local rearrangement of the sequence to the next permutation or returns false when there are no further permutations. The algorithm is as follows:

 template <class BidirectionalIterator> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last) { if (first == last) return false; // False for empty ranges. BidirectionalIterator i = first; ++i; if (i == last) return false; // False for single-element ranges. i = last; --i; for(;;) { BidirectionalIterator ii = i--; // Find an element *n < *(n + 1). if (*i <*ii) { BidirectionalIterator j = last; // Find the last *m >= *n. while (!(*i < *--j)) {} // Swap *n and *m, and reverse from m to the end. iter_swap(i, j); reverse(ii, last); return true; } // No n was found. if (i == first) { // Reverse the sequence to its original order. reverse(first, last); return false; } } } 

This uses constant space (iterators) for each generated permutation. Do you find that linear?

Answer 4

I think that to save your result (which will be an ordered list of N elements) there will be O (N) in memory, no?

Anyway, to answer your later question about choosing a random permutation, here is a technique that would be better than just producing all N! features in the list, say, and then randomly select an index. If we can just select the index randomly and generate the permutation associated with it, we are much better.

We can represent the dictionary order in your words / permutations and associate a unique number with them based on the word order / permutations of the appearance in the dictionary. For example, words on three characters will be

  perm. index 012 <----> 0 021 <----> 1 102 <----> 2 120 <----> 3 201 <----> 4 210 <----> 5 

You will see later why it’s easiest to use the numbers we made, but others can be placed with a bit more work.

To select one at random, you can randomly select your linked index from the range 0 ... N! -1 with uniform probability (the simplest implementation of this obviously cannot be solved even for moderately large N, I know, but I think there are decent workarounds), and then determine the permutation associated with it. Please note that the list starts with all permutations of the last elements of N-1, while maintaining the first digit equal to 0. After these possibilities are exhausted, we generate all those that begin with 1. After these next (N-1) ! permutations are exhausted, we generate those that start with 2. Etc. Thus, we can determine that the leading digit is Floor [R / (N-1)!], Where R is the index in the above sense. See also why we indexed zero too?

To generate the remaining N-1 digits in the permutation, let's say that we defined Floor [R / (N-1)!] = A0. Start with the list {0, ..., N-1} - {a0} (calculated subtraction). We need the Qth permutation of this list for Q = R mod (N-1) !. Except for the fact that there is no number there, this is exactly the same as the problem we just solved. Recurse

Answer 5

Perhaps you can, with factor numbers. You can extract the resulting permutation from it step by step, so that you never have to have the whole result in memory.

But the reason I started, maybe, is because I'm not sure what the growing behavior of the size of the factorial itself is. If it fits into a 32-bit integer or something like that, N is limited by a constant, so O (N) will be equal to O (1), so we should use an array for this, but I'm not sure how much it will be in terms of N.