如何使用 Python 生成置换线性扩展

Question

我想重现 this paper 中的实验。作者说他们使用了线性扩展，MathWorld对线性扩展的定义是：

偏序集合 P 的线性扩展是元素 p_1、p_2、... 的排列，使得 p_i< p_j 表示 i((1,2),(3,4))的线性扩展为1234、1324、1342、3124、3142、3412，所有在 2 之前有 1，在 4 之前有 3。

根据线性扩展的定义，我发现python这样的代码

import itertools

groups = [(1,2),(3,4)]
groupdxs = [i for i, group in enumerate(groups) for j in range(len(group))]
old_combo = ()
for dx_combo in itertools.permutations(groupdxs):
    if dx_combo <= old_combo: # as simple filter
        continue
    old_combo = dx_combo
    iters = [iter(group) for group in groups]
    print([next(iters[i]) for i in dx_combo])

根据线性扩展的定义，结果完全一样：这是结果：

[1, 2, 3, 4]
[1, 3, 2, 4]
[1, 3, 4, 2]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 4, 1, 2]

但是，我不知道如何根据论文实现这个：

论文中的线性扩展是按降序排列的，高分在前。
论文中的线性扩展似乎是基于字典而不是元组。

假设我有一个 Pandas 数据框 df:

import pandas as pd
data = [['a1', '10-11'], ['a2', '3-8'], ['a3', '4-6'],['a4','1-2'], ['a5','5-10']] 
df = pd.DataFrame(data, columns = ['A', 'B']) 
df

df:

     A   B
0   a1  10-11
1   a2  3-8
2   a3  4-6
3   a4  1-2
4   a5  5-10

我的问题是如何根据论文生成df的所有排列？论文中的示例线性扩展如下图所示：

预期结果如下：

[a1, a5, a3, a2, a4]
[a1, a2, a5, a3, a4] 
.
.
.

Answer 1

您可以通过使用递归生成器函数来镜像图的遍历以产生所需的结果：

纸上数据输出：

data = [['a1', '9'], ['a2', '5-8'], ['a3', '7'],['a4','0-10'], ['a5','4']]  
r = {a:list(map(int, b.split('-'))) for a, b in data}
vals = [(a, [[j, a] for j in range(b, b+1 if not x else x[0]+1)][::-1]) for a, (b, *x) in r.items()]
def get_combos(vals, c = []):
   v = [(i, [a, b]) for i, (a, b) in enumerate(vals) if a not in c]
   start = [a for i, (a, b) in v if all(b[0][0] > min([x for x, _ in k]) 
            for l, (j, k) in v if l != i)]
   if c:
      start = sorted(start, key=lambda x:r[x][-1], reverse=True)
   if not start:
      yield c
   else:
      yield from [i for b in start for i in get_combos(vals, c=c+[b])]

print(list(get_combos(vals)))

结果：

[['a1', 'a4', 'a2', 'a3', 'a5'], ['a1', 'a4', 'a3', 'a2', 'a5'], ['a1', 'a2', 'a4', 'a3', 'a5'], ['a1', 'a2', 'a3', 'a4', 'a5'], ['a1', 'a2', 'a3', 'a5', 'a4'], ['a1', 'a3', 'a4', 'a2', 'a5'], ['a1', 'a3', 'a2', 'a4', 'a5'], ['a1', 'a3', 'a2', 'a5', 'a4'], ['a4', 'a1', 'a2', 'a3', 'a5'], ['a4', 'a1', 'a3', 'a2', 'a5']]

您的数据输出：

data = [['a1', '10-11'], ['a2', '3-8'], ['a3', '4-6'],['a4','1-2'], ['a5','5-10']] 
r = {a:list(map(int, b.split('-'))) for a, b in data}
vals = [(a, [[j, a] for j in range(b, b+1 if not x else x[0]+1)][::-1]) for a, (b, *x) in r.items()]
print(list(get_combos(vals)))

结果：

[['a1', 'a5', 'a2', 'a3', 'a4'], ['a1', 'a5', 'a3', 'a2', 'a4'], ['a1', 'a2', 'a5', 'a3', 'a4'], ['a1', 'a2', 'a3', 'a5', 'a4'], ['a1', 'a3', 'a5', 'a2', 'a4'], ['a1', 'a3', 'a2', 'a5', 'a4']]

如何使用 Python 生成置换线性扩展

How to generate Permutation Linear Extension using Python

python

list

permutation