Permutation Id..? C++

Question

I am using permutation to generate a string (using each of its character) into "helloworld!", however it took...176791 to get to "helloworld!" Is there a ways so I can just input: 176791 to quickly permutate to "helloworld!"?

        ...
176790. helloworl!d
176791. helloworld!

My code:

#include <windows.h>
#include <string>
#include <iostream>
#include <algorithm>

int main( void )
{
    ::UINT64 Count = 0;
    std::string SomeString = "eohldo!lwrl";
    do
    {
        Count ++;
        std::cout << Count << ". " << SomeString << std::endl;
        if( SomeString == "helloworld!" )
            break;
    } while( std::next_permutation( SomeString.begin( ), SomeString.end( ) ) );

    ::getchar( );
    return( 0 );
};

How would you determine how far you need to jump? That is, how would you determine the number 176791? In this case you know it because you did the full iteration. — jogojapan, Nov 29 '12 at 03:41
You could certainly just not cout the preceding 176790 permutations.. — Karthik T, Nov 29 '12 at 03:46
@CPPNoob: Actually it is slow because of all those `std::cout`s, that is your bottleneck. — Jesse Good, Nov 29 '12 at 03:49
What jogojapan is saying is - how do you know WHICH permutation will give you your expected result? In this specific case it's 176790 but there's nothing in the math world that can direct permutations towards legible words — emartel, Nov 29 '12 at 03:49
@JesseGood Not just the `cout`'s; the *flushes* make it even *worse*. — WhozCraig, Nov 29 '12 at 03:52
heh, embedded system programmers create a hash-table for such performance hacks and hard-code every permutation into a hashtable. That way you can get to any permutation in the blink of an eye, on the expense of memory space — Aniket Inge, Nov 29 '12 at 03:52
Given a starting permutation, you can calculate how many permutations it will take to get a certain value, given a starting value. Think about how you'd calculate how many permutations it'd require to change the first character to the next lexicographically higher character. That's a start on the algorithm. — Yuushi, Nov 29 '12 at 03:53
@emartel Considering `std::next_permutation` generates permutations in lexicographic order, there certainly are ways to calculate the distance between two permutations. — Yuushi, Nov 29 '12 at 03:55
@Yuushi that is what I am asking for. But how can I achieve that? :( — CPPNoob, Nov 29 '12 at 03:56
@Yuushi he doesn't seem to be interested in knowing the sequence of operations, and since he needs to know the end result, why bother with the permutations at all in this case? — emartel, Nov 29 '12 at 03:57
Basically, I am trying to create an algorithm that could shift the inputted values into making the string value into "helloworld!". — CPPNoob, Nov 29 '12 at 03:58
That's what you want? In that case, why don't you just use `is_permutation` to check if the given string is a permutation of "helloworld!", and if it is, you just return "helloworld!"? Why permutate anything if you know the result in advance? — jogojapan, Nov 29 '12 at 04:01
Well, `is_permutation` does accept variables as arguments... — jogojapan, Nov 29 '12 at 04:04

score 3 · Accepted Answer · edited May 23 '17 at 12:04

I'm not sure what the question is about. Basically, it looks like you are looking for a way to "encode" a permutation by an integer. But it is not clear whether this encoding is required to be synchronized with permutation sequence generated by sequential calls to std::next_permutation. Is it? I.e do you require that number 176791 encodes a permutation produced by 176791 applications of std::next_permutation?

Permutations can be encoded by integers in several different ways. Properly constructed encodings will all occupy the same number of bits. But different encodings will might use different integers to encode the same permutation.

Anyway, if you don't care about a specific encoding method, then any permutation for N elements can be encoded in the following manner:

Imagine the canonical representation of the permutation: an array of N indexes that describe the new positions of the sequence's elements, i.e. index[old position] = new position.
Now simply interpret that array as a N-digit number in base N. I.e. the permutation is represented by an integer value
```
index[0]*N^0 +  index[1]*N^1 + index[2]*N^2 + ... + index[N-1]*N^(N-1)
```

Basically, the canonical array representation of the original permutation is packed into a sufficiently large integer value. (If N is a power of 2, this representation will simply pack the original array values into a bit-array). Both packing and unpacking is a straightforward process.

Unfortunately, the representation I describe above is not well-constructed. It requires more bits than necessary, since it attempts to "losslessly" encode index arrays with non-unique values. A valid representation of a permutation will not have repetitive values in the index array. This immediately means that the above representation is excessive. A more compact representation should be possible. Anyway, this should be a rather well-researched subject and a simple Google search should turn up lots of information on encoding permutations.

Here's a SO link that offers a much deeper analysis of this topic

Fast permutation -> number -> permutation mapping algorithms

I can understand that the question is a bit "abstract". Please let me rephrase. So it took 176791 permutation to permutate the string into "helloworld!". And the problem is that, it took few minutes (even without printf or cout). So the question is, is there any way where as I can simply input 176791 to quickly permutate or ( rotate, swap, etc ) to get the string to have the value of "helloworld!"? — CPPNoob, Nov 29 '12 at 03:52
@CPPNoob: Well, again, the question I'm asking is: how important is it to represent that specific permutation by integer `176791` specifically? My method described above will use the same number of bits, but it might end up representing the same permutation by a *different* integral value. Is that a problem or not? — AnT stands with Russia, Nov 29 '12 at 03:54
Well, thanks everyone for their input. :) I'll go do some more research — CPPNoob, Nov 29 '12 at 04:07
@CPPNoob: Take a look here: http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms — AnT stands with Russia, Nov 29 '12 at 04:09

Permutation Id..? C++

1 Answers1