如何使用Python生成置换线性扩展
如何使用Python生成置换线性扩展
提问于 2021-04-07 12:45:07
我想从本论文复制这个实验。作者说他们使用线性扩张，MathWorld的线性扩张的定义是：
偏序集P的线性扩张是元素p_1，p_2，…例如，偏序集((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 dataframe 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]
.
.
.回答 1
Stack Overflow用户
回答已采纳
发布于 2021-04-07 14:08:59
您可以通过使用递归生成器函数来反映图形的遍历，从而产生所需的结果：
关于纸张数据的输出：
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']]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/66986335
复制相关文章
相似问题
腾讯云开发者
