Ranking and Unranking binary Permutation with distance criteria

Question

I want to rank and unrank binary permutations with a distance criteria.

Example:

maxDistance := 2

Valid binary permutations consisting the elements 0011 are following:

0101 -> Rank 0

1010 -> Rank 1

0110 -> invalid because the first index of 0 is 0 but the second occurence of 0 has index 3. 3-0 > maxDistance

0011 -> invalid because the first occurence of 1 is at index 2 but the distance is 3.

distance is calculated, via equal elements index, of two adjecent equal elements doesnt differ more than abs(distance), but for the first occurence of an element the index+1 == distance. The maxDistance applies for 0 and 1. There can be unequal occurences of 0,1 in the binary permutation. Rank is the index of the given permutation in an ordered list of valid permutations.

to rank = binary permutation to indexnumber(Rank), maxDistance

to unrank = Rank+occurences 0+occurences 1+maxDistance to permutation

int calcMaxDistance(BitSet set){
  int max0 =0;
  int max1 =0;
  int lastIndex0 =0;
  int lastIndex1 =0;

  for(int i=0; i < set.size();i++){
    if(set.get(i)){
      if(lastIndex1 ==0 && max1 ==0){
        max1 = i+1;
      }else{
        if(i - lastIndex1 > max1){
          max1 = i - lastIndex1;
        }
      }
      lastIndex1 = i;
    }else{
      // Same structure for max0 like with max1
    }
  }
  return Math.max(max0,max1);
}

Has anybody an idea how to construct the algorithm?

btilly · Answer

Here is an implementation.

First, a top-down dynamic programming approach to analyzing the admissible permutations. If you have symbol counts n1, n2, ..., nk then this can take time as bad as O(n1*n2*...*nk).

def analyze_distance_perm(symbols, distance):
    s_count = {}
    for s in symbols:
        if s in s_count:
            s_count[s] += 1
        else:
            s_count[s] = 1
    starting_state = []
    for s, count in s_count.items():
        starting_state.append((s, 1, count))

    cache = {}
    def recur (remain, state):
        key = (remain, tuple(state))
        if key not in cache:
            if 0 == remain:
                cache[key] = {"c": 1, "t": None}
                for s, dist, left in state:
                    if distance < dist:
                        cache[key] = None
                        break
            else:
                next_state = []
                for i in range(len(state)):
                    s, dist, left = state[i]
                    if distance < dist:
                        next_state = None
                    elif next_state is not None:
                        next_state.append((s, dist+1, left))
                if next_state is None:
                    cache[key] = None
                else:
                    count = 0
                    transition = {}
                    for i in range(len(next_state)):
                        s, dist, left = next_state[i]
                        if 0 < left:
                            next_state[i] = (s, 1, left-1)
                            result = recur(remain-1, next_state)
                            if result is not None:
                                count += result['c']
                                transition[s] = result
                            next_state[i] = (s, dist, left)
                    if 0 == len(transition):
                        cache[key] = None
                    else:
                        cache[key] = {'c': count, 't': transition}

        return cache[key]
    return recur(len(symbols), starting_state)

With this analysis in hand, ranking/unranking is straightforward. (I chose to call the rank the number of permutations before, so the first one has rank 0. It is easy to adjust that if you want.)

def rank_perm(perm, analysis):
    if 0 == len(perm):
        return 0
    elif analysis is None or perm[0] not in analysis['t']:
        return None
    rank = 0
    for s, subanalysis in analysis['t'].items():
        if s != perm[0]:
            rank += subanalysis['c']
        else:
            subrank = rank_perm(perm[1:], subanalysis)
            if subrank is None:
                return None
            else:
                return rank + subrank

def perm_at_rank(rank, analysis):
    return list(reversed(_perm_at_rank(rank, analysis)))

def _perm_at_rank(rank, analysis):
    if analysis is None or analysis['t'] is None:
        if rank == 0:
            return []
        else:
            return None

    for s, subanalysis in analysis['t'].items():
        if rank < subanalysis['c']:
            subperm = _perm_at_rank(rank, subanalysis)
            if subperm is None:
                return None
            else:
                subperm.append(s)
                return subperm
        else:
            rank -= subanalysis['c']

And here is your original example showing it can rank and unrank every permutation correctly.

analysis = analyze_distance_perm('0011', 2)
for i in range(analysis['c']):
    perm = perm_at_rank(i, analysis)
    print(i, perm, rank_perm(perm, analysis))

And a less trivial example.

analysis = analyze_distance_perm('0001122', 4)
for i in range(analysis['c']):
    perm = perm_at_rank(i, analysis)
    print(i, perm, rank_perm(perm, analysis))

Ranking and Unranking binary Permutation with distance criteria

1 Answers