Crytograph - Decryption

Hello,
I am now trying to solve a question on decryption. does anyone has any idea how the algo will be like for this question?
Problem Description:
In a war, a commander sends commands to his troops. The commander will encrypt the message so that even if the message is captured by the enemy, the enemy will not be able to understand it.
One simple yet effective way of encrypting a message is to remove all the spaces and punctuation marks, and then to rearrange all the letters. For example if the original message (after removing all the spaces and punctuation marks) is ABCDEF, it can be rearranged into BCAEDF, i.e., the 1st letter of the encrypted message is the 2nd letter of the original message; the 2nd letter of the encrypted message is the 3rd letter of the original message; the 3rd letter of the encrypted message is the 1st letter of the original message, and so on and so forth. This rearrangement can be represented using a sequence of numbers (2, 3, 1, 5, 4, 6). This sequence is called a permutation of 1, 2, 3, 4, 5, 6 because it is a rearrangement of 1, 2, 3, 4, 5, 6.
In fact for every permutation of 1, 2, 3, 4, 5, 6 you can get a different encrypted message. For example if the sequence is (3, 4, 2, 5, 6, 1) the encrypted message will be CDBEFA. One way to safely transmit the original message to the receiver is to pick a permutation, and then transmit both the permutation and the encrypted message. Once the receiver receives the message, he/she can reverse the encryption process and get the original message. However, the enemy are not fools. If the enemy captures the message, they can easily guess the method used and decrypt the message. To make it harder for the enemy to guess the encryption method, an intelligent commander comes up with the following scheme:
Instead of sending the permutation, he sends a magic number. To determine the magic number, the commander first lists all the possible permutations in the following order: for any two permutations p1 and p2, the one with the smallest first number is listed first; if they have the same first number then he will compare the second numbers; if the second numbers are the same, he will compare third numbers; and so on and so forth. Then the commander numbers the very first permutation in the list as 0; the next one as 1; .... and as a result every permutation gets a number. Finally, the commander chooses one of these assigned numbers to be the magic number, and the receiver decodes the message using the permutation that corresponds to that magic number.
For example, the following are some of the permutations of 1, 2, 3, 4, 5, 6
0 (1, 2, 3, 4, 5, 6)
1 (1, 2, 3, 4, 6, 5)
2 (1, 2, 3, 5, 4, 6)
3 (1, 2, 3, 5, 6, 4)
4 (1, 2, 3, 6, 4, 5)
... ......
146 (2, 3, 1, 5, 4, 6)
... ......
297 (3, 4, 2, 5, 6, 1)
... ......
719 (6, 5, 4, 3, 2, 1)

Once the receiver receives the message, he/she needs to use the magic number to discover the corresponding permutation, and then use that permutation to decrypt the message. However, trying to find a magic number's corresponding permutation is not easy by hand. It is desirable to write a program that automatically computes the permutation given the magic number.
Input
The input consists of multiple lines, with each line consisting of two integers, n and m, that are separated by a single space. n is the length of the encrypted message (i.e., the number of numbers in the permutation), and m is the magic number. All numbers do not exceed the maximum range of long (i.e., 2 to the power of 63).
Output
For every magic number, print the corresponding permutation on one line. You shall use single spaces to separate all numbers on the same line and shall not have any extra space in front of the first number or after the last number.
Sample Input
6 0
6 146
6 297
6 719
5 1
5 4
Sample Output
1 2 3 4 5 6
2 3 1 5 4 6
3 4 2 5 6 1
6 5 4 3 2 1
1 2 3 5 4
1 2 5 3 4

Hi.
I'll try to provide a hint here (looks lika a school lab-assignment and I wouldn't want to provide the full solution.).
Consider the first letter {X,..,..,..,..,..}, that will be fairly easy to figure out, since you know that this will be 1 for the first 1/m:th parh (i.e. it would be 1 for the first sixth of the entire keyspace, and 2 for the second sixth, and so on in your example).
This would give you a quite easy loop, just loop through all the positions, figuring out what the next number would be. Remember however, that the second and following positions will not be distributed with a 1/m:th distribution, since the available space for those characters are less.
Hope this helps, feel free to post any further questions.
/Peter

Hello,
Peter thanks for ur help but i don't really understand what u mean by "1/m:th parh (i.e. it would be 1 for the first sixth of the entire keyspace, and 2 for the second sixth, and so on in your example).". Sorry, is it possible if u explain it again...=) thanks!
cynthia =)

Originally posted by Peter Kristensson:
Hi.
I'll try to provide a hint here (looks lika a school lab-assignment and I wouldn't want to provide the full solution.).
Consider the first letter {X,..,..,..,..,..}, that will be fairly easy to figure out, since you know that this will be 1 for the first 1/m:th parh (i.e. it would be 1 for the first sixth of the entire keyspace, and 2 for the second sixth, and so on in your example).
This would give you a quite easy loop, just loop through all the positions, figuring out what the next number would be. Remember however, that the second and following positions will not be distributed with a 1/m:th distribution, since the available space for those characters are less.
Hope this helps, feel free to post any further questions.
/Peter

Right. I'll give it another shot.
Take this example; a four letter word. keys are like this {1,2,3,4} or {4,3,2,1} or whatever. You know for a fact that these keys can be produced in 24 different ways (n!). You also know that according to your "sorting" of the keys, the first fourth (first six keys) of them will have a 1 in the first position.
You also know that the next fourth (the next six keys) will have 2 in the first position. The list of keys looks something like this:
First six positions:
{1,2,3,4}
{1,2,4,3}
{1,3,2,4}
{1,3,4,2}
{1,4,2,3}
{1,4,3,2}
The next six positions:
{2,1,3,4}
{2,1,4,3}
{2,3,1,4}
{2,3,4,1}
{2,4,1,3}
{2,4,3,1}
and so on.
So you see, with a little mathematics, you can easily determine which charater is to be placed in the first position, and after that you can remove that character and (almost) just as easily determine the second character, and so on and so forth.
For clarity's sake, I'll just give the formula for the first character and let you figure out the remaining ones:
m = magic number
n = length of word
x = first character in key
x = ((m-1) 'div' (n!/n)) + 1
Does this make it any clearer?
/Peter