online advertising

Sunday, September 14, 2014

UVa Problem 941 - Permutations

Problem:

Please find the problem here.

Solution:

For simplicity, let's assume the input is always the sequences of capital letters, ABCDE...

We will solve this problem recursively. First, note that it is easy to determine the first digit of the permutation. Suppose the input has only 3 letters and we wanted the 4th permutation, we know that the first digit must be C. This is because there are only 3 choices for the first digit, and therefore, the first digit must be distributed look like this

[AXX, AXX], [BXX, BXX], [CXX, CXX]

Therefore, the 4th permutation (remember we have the 0th permutation) must start from C, as it fall into the last group.

The discussion generalize to n digits case easily. In that case the list of all permutations falls into n groups, each of size (n-1)!, we just simply have to find out which group it is and take that digit.

Suppose the kth letter is chosen. Now we wanted to find the rest. If we could formulate the problem of finding the rest as an instance of this same problem, we could solve this recursively. And yes we can! The rest is just the (n - k(n-1)!)th permutation of the remaining unused letters.

With that algorithm, the code is not hard to write. Note that the problem specify the input string is NOT sorted and requires lexicographical order, so we need to sort the string ourselves, and that is a simple sort since there are only 20 letters.

Code: 

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=882

#include "UVa941.h"

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void compute_permutation(long long num_permutation, string ordering_string, vector<unsigned int> unused_positions)
{
    if (unused_positions.size() == 1)
    {
        cout << ordering_string[*(unused_positions.begin())];
    }
    else
    {
        // Compute (size - 1)!
        long long factorial = 1;
        for (unsigned int i = 1; i < unused_positions.size(); i++)
        {
            factorial *= i;
        }

        int position = num_permutation / factorial;

        vector<unsigned int>::iterator p = unused_positions.begin();
        for (int j = 0; j < position; j++)
        {
            p++;
        }
        cout << ordering_string[*p];

        unused_positions.erase(p);
        num_permutation -= position * factorial;
        compute_permutation(num_permutation, ordering_string, unused_positions);
    }
}

void compute_permutation(long long num_permutation, string ordering_string)
{
    vector<unsigned int> unused_positions;
    for (unsigned int i = 0; i < ordering_string.length(); i++)
    {
        unused_positions.push_back(i);
    }
    compute_permutation(num_permutation, ordering_string, unused_positions);
}

int UVa941()
{
    int number_of_cases;
    cin >> number_of_cases;
    for (int c = 0; c < number_of_cases; c++)
    {
        long long num_permutation;
        string ordering_string;
        cin >> ordering_string;
        for (unsigned int i = 0; i < ordering_string.length(); i++)
        {
            for (unsigned int j = i + 1; j < ordering_string.length(); j++)
            {
                if (ordering_string[i] > ordering_string[j])
                {
                    char temp = ordering_string[i];
                    ordering_string[i] = ordering_string[j];
                    ordering_string[j] = temp;
                }
            }
        }
        cin >> num_permutation;

        // Computing ordering recursively
        compute_permutation(num_permutation, ordering_string);
        cout << endl;
    }

    return 0;
}

No comments :

Post a Comment