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?
CodePudding user response:
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))