我想使用距離標準對二進制排列進行排名和取消排名。
例子：
maxDistance := 2
組成元素的有效二進制排列0011如下：
0101-> 排名 0
1010-> 排名 1
0110-> 無效，因為 的第一個索引0為 0，但第二次0出現的索引為 3。3-0 > maxDistance
0011-> 無效，因為第一次出現1在索引 2 處，但距離為 3。
distance通過相等元素索引計算兩個相鄰相等元素的差異不超過abs(distance)，但對于第一次出現的元素index 1 == distance. maxDistance適用于0和。在二進制排列中
1可能出現不相等的。是給定排列在有效排列的有序串列中的索引。0,1Rank
to rank = 二進制排列到 indexnumber(Rank), maxDistance
to unrank = Rank occurrences occurrences 0 1maxDistance 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);
}
有人知道如何構造演算法嗎？
uj5u.com熱心網友回復：
這是一個實作。
首先，一種自上而下的動態規劃方法來分析可接受的排列。如果您有符號計數n1, n2, ..., nk，那么這可能需要像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)
有了這個分析，排名/取消排名就很簡單了。（我之前選擇將排名稱為排列數，因此第一個排名為 0。如果您愿意，可以輕松調整。）
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']
這是您的原始示例，顯示它可以正確地對每個排列進行排名和取消排名。
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))
還有一個不那么瑣碎的例子。
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))
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/507878.html