Party Presents - A possible new problem

This is a lexicographic ordering problem with the added twist that not all possible strings are allowed in the ordered list. I have developed a generator which uses random numbers to create about ten sets of data, of varying difficulty, together with the corresponding solutions. The run time is negligible. The example below is a typical set of problem data, with solutions.

The following is a draft problem description:

At a children's party the children all have an opportunity to choose a present before going home. The host of the party thought up a novel way of allowing the children to choose their presents. The presents were arranged on a circular carousel that allowed the children to see the presents one at a time as the carousel rotated. Behind each present was an alphabetic letter to mark the position of the present on the carousel. When the carousel rotates, present A is shown first, followed by presents B, C , D and so on. There are the same number of presents as children.

During the party the carousel is rotated several times so that the children can see the presents and their position on the carousel. Naturally each child decides which present they are going to choose and remembers the letter denoting its position on the carousel. Towards the end of the party the host draws lots (secretly) to determine the order in which the children will choose their presents. One by one they are brought into the room with the carousel to choose a present but they do not know how many children have chosen before them. They are told that the carousel will rotate once, starting at present A (if it is still there). The child must choose a present before the end of the rotation is reached, otherwise they will have no present to take home.

Each child hopes that their chosen present is still there. When the corresponding letter is reached they exitedly grab their present, if it is still available. If their chosen present has already gone the child begins to panic. They were so intent on getting their chosen present that they hadn't decided what to do if it wasn't there. Knowing that they could end up without a present, they take the very next present that is still available. There is always the possibility of being able to swap it with another child after the party. We will assume that every child applies this same strategy in choosing a present. We will also assume that every child is able to choose a present before the carousel stops. (It wouldn't be nice to leave any little children without a present!)

Consider a party with 5 children. Imagine that the presents are taken in the order B, E, C, A and D, so the first child to choose takes present B and the fifth child takes present D. Imagine that the presents which the children had hoped to choose were B, E, B, A and B (with the children listed in the same order). We will refer to this set of presents as a wishlist and will write it without commas for convenience. So this wishlist is BEBAB. It is easy to see how this wishlist gives rise to the actual presents taken. The first child wants to choose present B and is successful since no presents have yet been chosen. The second child wants present E and is also successful. The third child wants present B but this has already gone. The child takes the next available present, which is C. The fourth child wants present A and is successful. The fifth child wants present B, which has been taken. The next available present is D (because C has also been taken).

There are 5 children and each could hope to choose any of the 5 presents. This means that there are 3125 (5^5) possible wishlists. It is easy to generate these and to verify that only 8 of them would give rise to the presents which were taken by the children. In lexicographic order, these are: BEBAA, BEBAB, BEBAC, BEBAD, BECAA, BECAB, BECAC and BECAD. If we number these from 1 to 8 we can see that BECAB is number 6.

The first line of the problem gives the number N of sets of data. N lines follow. Each of these has a string followed by a position. The string is the list (in order) of presents taken by the children. The number of letters (hence presents) is the same as the number of children. You have to find the wishlist at the given position in the lexicographic order of all wishlists which match the list of presents taken. For example, when the presents taken are ABCDFE, the 40th wishlist is AABDFE. Give the answers, separated by spaces, as a single string.

Example:

input:
10
ABCDFE 40
EBHCDFGAI 1219
JDCGEBHFIKA 2189
DKGLEFMHNICJAB 26809
LIHDBFCAJKMNGOPE 626490
RKCODEJGHIFAPLMBNQ 10956203
LMNQEKRDOASBCTIPFGHJ 52491336
NGBLAJMOEPIRQHVKCSTUDF 338251306
DSKXEFITJNMLUHOPQRVGWABC 13131481866
QEWXRGZTYKJHILAMFNOPSUBVCD 106068782044

answer:
AABDFE EBHCCDEAD JDCGEBHDDJA DKGKEELHNECGAA LIHDBFCAHIKJGFME RKCODDJGGICAPEHAGI LMLQEKRDLAQACTIOCDFF NGBLAJMMEOIRPGVGCNKUBD DSKXEEITJNMIUHJJIMUGNABC QEWWQGZTXKJGIKAGFIIJFUAGAD

Rodion, Hi.

Although this problem is harder than my previous submissions it is not as hard as it might appear from first reading. I hope that people will not be put off by this and will give the problem some thought.

I am a firm believer in trying small examples with pencil and paper before designing a suitable algorithm.

It should be fairly easy to get the correct values for the first few tests by using fairly inefficient algorithms. Hopefully this will prompt people to go on to find something better.

The code has now been e-mailed to you.

Rodion,

Thanks for getting the problem in place so quickly. I've checked it out and everything seems fine. However, before I even knew it was in place Mathias has posted the first solution. That is impressive but not entirely surprising. This is also further evidence that all is working.