Find order of an array using minimum memory and time

Question

Let's say i have an array of 5 elements. My program knows it's always 5 elements and when sorted it's always 1,2,3,4,5 only.

As per permutations formula i.e n!/(n-r)! we can order it in 120 ways.

In C++ using std::next_permutation I can generate all those 120 orders.

Now, my program/routine accepts an input argument as a number in the range of 1 to 120 and gives the specific order of an array as output.

This works fine for small array sizes as i can repeat std::next_permutation until that matches input parameter.

The real problem is, How can i do it in less time if my array has 25 elements or more? For 25 elements, the number of possible orders are : 15511210043330985984000000.

Is there a technique that I can easily find the order of numbers using a given number as input?

Thanks in advance :)

I'm confused what you want. It kind of sounds like if I enter 120, you want 1, 2, 3, ..., 119, 120. — chris, Aug 27 '16 at 23:25
Given you provide no context as to why you need this one can only come to the conclusion that this is a school assignment... — rbaleksandar, Aug 27 '16 at 23:25
@chris, If i enter 120, it's 5,4,3,2,1, Below all the possibilities. List has 120 entries. {1,2,3,4,5} {1,2,3,5,4} {1,2,4,3,5} {1,2,4,5,3} {1,2,5,3,4} {1,2,5,4,3} ........................{5,2,1,3,4} {5,2,1,4,3} {5,2,3,1,4} {5,2,3,4,1} {5,2,4,1,3} {5,3,4,2,1} {5,4,1,2,3} {5,4,1,3,2} {5,4,2,1,3} {5,4,2,3,1} {5,4,3,1,2} {5,4,3,2,1} — musk's, Aug 27 '16 at 23:28
@rbaleksandar it's not a school assignment and i think context is not necessary. I just want to solve the problem the way I was expecting. — musk's, Aug 27 '16 at 23:31
This is not solvable without more information. A sequence of permutations does not need to generate values in any particular order so long as it generates all permutations without repetitions. Your 5th permutations need not be my 5th permutation as we are using different algorithms. — Richard Critten, Aug 27 '16 at 23:42
Have a look at [this question](http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms). — , Aug 27 '16 at 23:44
[here](http://math.stackexchange.com/questions/60742/finding-the-n-th-lexicographic-permutation-of-a-string) is the mathematic solution for your problem. — lnyng, Aug 27 '16 at 23:48
@RichardCritten No problem, take any one algorithm that generates permutations and provide me a solution how can i find Nth permutation from a list of 25 elements quickly. — musk's, Aug 27 '16 at 23:50

score 0 · Answer 1 · answered Aug 27 '16 at 23:49

I have had a similar problem where I was storing lots of row in a Gtk TreeView and did not want to go over all of them every time I want to access a row by its position and not by its reference.

So, I created a map of the positions of the row so I could easily identify them by the parameter I needed. So, my suggestion to this is you go over all permutations once and map every std::permutation in an array (I used a std::vector), so you can access it by myVector[permutation_id].

Here is my way I have done the mapping:

vector<int> FILECHOOSER_MAP;
void updateFileChooserMap() {
    vector<int> map;
    TreeModel::Children children = getInterface().getFileChooserModel()->children();
    int i = 0;
    for(TreeModel::Children::iterator iter = children.begin(); iter != children.end(); iter++) {
        i++;
        TreeModel::Row row = *iter;
        int id = row[getInterface().getFileChooserColumns().id];
        if( id >= map.size()) {
            for(int x = map.size(); x <= id; x++) {
                map.push_back(-1);
            }
        }
        map[id] = i;
    }
    FILECHOOSER_MAP = map;
}

So in your case you would just iterate over the permutations like this and you can map them in a way that allows you accesing them by their id.

I hope this helps you :D regards, tagelicht

score 0 · Accepted Answer · edited Apr 13 '17 at 12:19

This is an example c++ implementation of the algorithm mentioned in this link:

#include <vector>
#define ull unsigned long long

ull factorial(int n) {
    ull fac = 1;
    for (int i = 2; i <= n; i++)
        fac *= i;
    return fac;
}

std::vector<int> findPermutation(int len, long idx) {
    std::vector<int> original = std::vector<int>(len);
    std::vector<int> permutation = std::vector<int>();
    for (int i = 0; i < len; i++) {
        original[i] = i;
    }

  ull currIdx = idx;
  ull fac = factorial(len);
  while (original.size() > 0) {
      fac /= original.size();
      int next = (currIdx - 1) / fac;
      permutation.push_back(original[next]);
      original.erase(original.begin() + next);
      currIdx -= fac * next;
  }
  return permutation;
}

The findPermutation function accepts the length of the original string and the index of the required permutation, and returns an array that represents that permutation. For example, [0, 1, 2, 3, 4] is the first permutation of any string with length 5, and [4, 3, 2, 1, 0] is the last (120th) permutation.

Find order of an array using minimum memory and time

2 Answers2