CODEWITHSUNDEEP
calgorithmpermutation
solarsoul1776
solarsoul1776

Reputation: 9

Algorithm for finding n-2 permutation (with repeats) given lexicographic index

I am trying to find a method to determine a permutation of n-2 numbers, repetitions being allowed) from a set of n numbers, given its lexicographic index. One reason why we are doing this is to find Prufer codes, given an index. Considering a set of numbers as [1,2,3,4] we shall get a set of n-2 permutations as [1,1], [1,2], [1,3], [1,4]......[4,3], [4,4]. My question is if there is a methodology for getting a permutation like this given the index as an input, without enumerating all the permutations. I looked at the methods in this link Finding the index of a given permutation but this may have issues with permutations of n-2 objects. Thanking you.

Upvotes: 0

Views: 156

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23945

Here's some JavaScript code for m69's idea:

function f(rank, arr){
  var n = arr.length,
      res = new Array(n - 2).fill(arr[0]),
      i = n - 3;
 
  while (rank){
    res[i--] = arr[rank % n];
    rank = Math.floor(rank / n); 
  }
  
  return res;
}

console.log(f(64, ['a','b','c','d','e']));

Upvotes: 0

m69 ''snarky and unwelcoming''
m69 ''snarky and unwelcoming''

Reputation: 12324

The permutation with a given rank from a set of n numbers can be calculated by converting the rank to a base-n number, and interpreting its digits as 0-based indexes:

set: [1,2,3,4]
0-based rank: 9
9 in base-4: 21
0-based indexes: [2,1]
permutation: [3,2]

set: [a,b,c,d,e]
0-based rank: 64
64 in base-5: 224
0-based indexes: [2,2,4]
permutation: [c,c,e]

Something like this should do the trick, where set is an array of int containing n numbers, and perm is an array of int large enough to hold n-2 numbers: 

void permutation(int *set, int n, int rank, int *perm) {
    for (int k = n - 2; k > 0; --k) {
        perm[k - 1] = set[rank % n];
        rank /= n;
    }
}

(The above code assumes valid input)

Upvotes: 3

DvTr
DvTr

Reputation: 347

This is not a programming problem but more about understanding. A Prufer sequency it's a serie or linear application used to label each posible permutation of a set of numbers, beign each identification unique; so, you can define your Prufer sequency for [a0, a1, a2, ..., an-1] as, for example

S = [a0,a1, ..., an-1], S in N

S -Prufer-> S x S

0 --------> [a0, a0]
1 --------> [a0, a1]
      ...
n-1 ------> [a0, an-1]
n --------> [a1, a0]
n+1 ------> [a1, a1]
      ...
2n-1 -----> [a1, an-1]
2n -------> [a2, a0]
2n+1 -----> [a2, a1]

and so on... Then, in a general way, you can just determine permutation with index i as

P(i) = [a_sub_(i/n), a_sub(i modulus n)].

Note that this Prufer serie as example it's just a trivial one: you can define your own, keeping in mind that it must always identify the whole permutation set and as well make each identification unique (that is, a biyective linear application in basic Algebra)

Upvotes: 0

Related Questions