您如何以根据元素转换成本排序最小化连续集合之间的变化的方式对集合进行排序？
How do you sort sets in such a way that changes between consecutive sets are minimized according to an element transition cost ordering?
形式化一点：假设我们有一个有序的集合列表，列表中的每个集合都是集合 S 的一个子集。接下来，我们说如果连续的一对集合有一个元素包含在一个集合中，而不是另一个集合中，对于该对，元素的转换计数为 1。否则，此转换计数为 0。我们还将说集合 S 中的元素存在总排序 T。您将如何对集合列表进行排序，以使每个元素的总转换计数（对于有序集合列表中的每个连续对）按照集合 S 的排序提供的顺序排列优先级？
例如，假设我们要排序的集合是给定集合（所有子集）的幂集，减去任意数量的集合。对于我的应用程序，这表示生成剩余的实验，其中 n 个解释变量打开或关闭（由集合包含表示），可能已经进行了一些实验。排序中使用的变量的排序是切换变量的成本排序，我们正在尝试最小化剩余实验集的总转换成本。
from itertools import chain, combinations
def powerset(iterable):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
# fields ordered by decreasing difficulty to swap
difficulty_ordering = ['a', 'b', 'c', 'd']
field_powerset = list(powerset(difficulty_ordering))
[print(subset) for subset in field_powerset]
这将是：
()
('a',)
('b',)
('c',)
('d',)
('a', 'b')
('a', 'c')
('a', 'd')
('b', 'c')
('b', 'd')
('c', 'd')
('a', 'b', 'c')
('a', 'b', 'd')
('a', 'c', 'd')
('b', 'c', 'd')
('a', 'b', 'c', 'd')
如果我们任意删除一些：
field_powerset = random.sample(field_powerset, random.randrange(len(field_powerset)))
我们得到：
('a', 'b', 'd')
('a', 'd')
('b',)
()
('b', 'c', 'd')
('a', 'b', 'c', 'd')
('a', 'c')
('b', 'c')
('b', 'd')
('c', 'd')
('a', 'b', 'c')
('d',)
现在我们如何使用 difficulty_ordering 获得与此大致相似的排序结果？
()
('c', 'd')
('d',)
('b',)
('b', 'c')
('b', 'c', 'd')
('b', 'd')
('a', 'b', 'd')
('a', 'b', 'c', 'd')
('a', 'b', 'c')
('a', 'c')
('a', 'd')
# 1 a transition, 2 b transitions, 6 c transitions, 5 d transitions
如果可能的话，我不想重新实现整个排序，但我不确定这个想法是否可以用 python 的排序“关键函数”来实现。
但是在手动解决问题之后，感觉我可以遵循启发式来获得一个好的解决方案：
看来您首先需要“锁定”集合的范围，方法是首先最小化第一个字段的转换量。所以首先你将列表细分（由 # 表示的细分）列表分为 'a' 和没有
的列表
('b',)
()
('b', 'c', 'd')
('b', 'c')
('b', 'd')
('c', 'd')
('d',)
#
('a', 'b', 'd')
('a', 'd')
('a', 'b', 'c', 'd')
('a', 'c')
('a', 'b', 'c')
以后您只能在它们的范围内移动这些元素。然后你继续'b'并将这些范围进一步细分为有和没有两个，但现在它需要“没有b，有b，有b没有b”以完全减少过渡
()
('c', 'd')
('d',)
#
('b',)
('b', 'c', 'd')
('b', 'c')
('b', 'd')
#
('a', 'b', 'd')
('a', 'b', 'c', 'd')
('a', 'b', 'c')
#
('a', 'd')
('a', 'c')
然后是 c，进一步翻转每个部分没有 c 的 c
()
('d',)
#
('c', 'd')
#
('b', 'c', 'd')
('b', 'c')
#
('b',)
('b', 'd')
#
('a', 'b', 'd')
#
('a', 'b', 'c', 'd')
('a', 'b', 'c')
#
('a', 'c')
#
('a', 'd')
最后是 'd'，但这里有点不同，因为我们认为我们只是交换我们正在细分的每个细分的 with/without 的顺序。但在某些时候，您可能不想具体地遵循这一点，例如上面的第三个细分。如果我们稍微打破规则，我们会在这里得到一个完全最优的解决方案：
()
#
('d',)
#
('c', 'd')
#
('b', 'c', 'd')
#
('b', 'c')
#
('b',)
#
('b', 'd')
#
('a', 'b', 'd')
#
('a', 'b', 'c', 'd')
#
('a', 'b', 'c')
#
('a', 'c')
#
('a', 'd')
选择不交换该细分中的 with/without 排序可以降低总成本排序。因此，从本质上讲，在决定当前细分的 with/without 顺序时，您似乎需要匹配前一组对当前元素的包含。这部分让我觉得递归并不是解决问题的好方法。但是，我不确定目前是否可以将这些思想和规则完全表述为python动态规划算法。
您的问题简化为 single-source shortest path problem on an undirected graph with natural number weights, which is addressed by Thorup, 1999, and is solvable in O(E) time. Alternatively, if your state transition costs are not natural numbers, then it is addressed by Fredman & Tarjan, 1984 并且可以在 O(E + Vlog(V)) 时间内解决。
想象一下将此集合中的每个对象布置为图形上的一个顶点。例如，如果您有三个 'states' (x_1, x_2, x_3)，那么您有八个由幂集表示的基础配置：
()
(x_3)
(x_2)
(x_1)
(x_2, x_3)
(x_1, x_3)
(x_1, x_2)
(x_1, x_2, x_3)
这八种配置代表图形上的节点。想象一下，将图形限制为转换成本 1。然后您将得到以下配置：
() -> (x_1) (x_2) (x_3)
(x_1) -> (x_1, x_2) (x_1, x_3), ()
(x_2) -> (x_1, x_2) (x_2, x_3), ()
(x_3) -> ...
在这种情况下，您要优化的是遍历此配置中每个顶点的最短路径。这是您在此处提出的问题的简化版本。
为了完成这个问题，想象一下这种情况的完整图表，K_3。在此配置下，您可以根据切换每个状态的相对困难来分配边权重。例如，如果 (x_1, x_2, x_3) 按增加的难度排序，这样 x_2 和 x_3 永远不会覆盖 x_1 上的转换，则按 2 的幂分配：x_1 成本为 4，x_2 成本为 2，x_3 成本为 1，从而产生正确的顺序。当有多个状态要转换时如何分配成本是一种设计选择，取决于您的问题中未共享的实现细节。
为了适应已经涵盖的配置，您可以像上面那样简单地将它们从幂集中删除，并且re-run剩余顶点的最短路径解决方案。
看来我能够实现我上面描述的贪心动态规划算法，它对我的目的有效。我不会说这是问题的最佳解决方案，也不确定时间复杂度（O(m^2*n) 也许吧？其中 m 是字段数，n 是要订购的集合数）。但与将解决方案映射到图论问题相比，它的实施认知负担更小。
from itertools import chain, combinations
import random
def powerset(iterable):
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
def flatten(to_flatten):
for x in to_flatten:
if hasattr(x, '__iter__') and not isinstance(x, str) and not isinstance(x, tuple):
for y in flatten(x):
yield y
else:
yield x
# order a list of tuples such that the transition between elements is minimized
# prioritizing elements in the order of field_order
def minimize_transitions(tuple_list, field_order):
tuple_lists = [tuple_list]
# whether the field is included last (true), or not included last (false), in the previous list
for field in field_order:
next_tuple_lists = []
ending_with = False
for tuple_list in tuple_lists:
if len(tuple_list) == 1:
ending_with = field in tuple_list[0]
next_tuple_lists.append(tuple_list)
elif len(tuple_list) == 0:
continue
else:
if ending_with:
next_tuple_lists.append(list(filter(lambda this_tuple: field in this_tuple, tuple_list)))
next_tuple_lists.append(list(filter(lambda this_tuple: field not in this_tuple, tuple_list)))
else:
next_tuple_lists.append(list(filter(lambda this_tuple: field not in this_tuple, tuple_list)))
next_tuple_lists.append(list(filter(lambda this_tuple: field in this_tuple, tuple_list)))
ending_with = not ending_with
tuple_lists = next_tuple_lists
return flatten(tuple_lists)
# fields ordered by decreasing difficulty to swap
field_order = ['a', 'b', 'c', 'd', 'e']
field_powerset = list(powerset(field_order))
field_powerset = random.sample(field_powerset, random.randrange(len(field_powerset)))
print("Starting sets:")
[print(subset) for subset in field_powerset]
print()
print("Ordering for minimized transitions:")
field_powerset = minimize_transitions(field_powerset, field_order)
[print(subset) for subset in field_powerset]
Starting sets:
('a', 'c', 'e')
('d', 'e')
('c', 'e')
('a', 'c', 'd')
('a', 'b', 'd', 'e')
('c', 'd', 'e')
('b', 'c', 'd', 'e')
('b', 'd')
('a', 'b', 'c', 'd', 'e')
('a', 'c', 'd', 'e')
('a', 'b', 'd')
('e',)
('a', 'b', 'c')
()
('a', 'b', 'c', 'e')
('a', 'b', 'c', 'd')
('a', 'b', 'e')
('d',)
Ordering for minimized transitions:
()
('e',)
('d', 'e')
('d',)
('c', 'd', 'e')
('c', 'e')
('b', 'c', 'd', 'e')
('b', 'd')
('a', 'b', 'd')
('a', 'b', 'd', 'e')
('a', 'b', 'e')
('a', 'b', 'c', 'e')
('a', 'b', 'c')
('a', 'b', 'c', 'd')
('a', 'b', 'c', 'd', 'e')
('a', 'c', 'd', 'e')
('a', 'c', 'd')
('a', 'c', 'e')
形式化一点：假设我们有一个有序的集合列表，列表中的每个集合都是集合 S 的一个子集。接下来，我们说如果连续的一对集合有一个元素包含在一个集合中，而不是另一个集合中，对于该对，元素的转换计数为 1。否则，此转换计数为 0。我们还将说集合 S 中的元素存在总排序 T。您将如何对集合列表进行排序，以使每个元素的总转换计数（对于有序集合列表中的每个连续对）按照集合 S 的排序提供的顺序排列优先级？
例如，假设我们要排序的集合是给定集合（所有子集）的幂集，减去任意数量的集合。对于我的应用程序，这表示生成剩余的实验，其中 n 个解释变量打开或关闭（由集合包含表示），可能已经进行了一些实验。排序中使用的变量的排序是切换变量的成本排序，我们正在尝试最小化剩余实验集的总转换成本。
from itertools import chain, combinations
def powerset(iterable):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
# fields ordered by decreasing difficulty to swap
difficulty_ordering = ['a', 'b', 'c', 'd']
field_powerset = list(powerset(difficulty_ordering))
[print(subset) for subset in field_powerset]
这将是：
()
('a',)
('b',)
('c',)
('d',)
('a', 'b')
('a', 'c')
('a', 'd')
('b', 'c')
('b', 'd')
('c', 'd')
('a', 'b', 'c')
('a', 'b', 'd')
('a', 'c', 'd')
('b', 'c', 'd')
('a', 'b', 'c', 'd')
如果我们任意删除一些：
field_powerset = random.sample(field_powerset, random.randrange(len(field_powerset)))
我们得到：
('a', 'b', 'd')
('a', 'd')
('b',)
()
('b', 'c', 'd')
('a', 'b', 'c', 'd')
('a', 'c')
('b', 'c')
('b', 'd')
('c', 'd')
('a', 'b', 'c')
('d',)
现在我们如何使用 difficulty_ordering 获得与此大致相似的排序结果？
()
('c', 'd')
('d',)
('b',)
('b', 'c')
('b', 'c', 'd')
('b', 'd')
('a', 'b', 'd')
('a', 'b', 'c', 'd')
('a', 'b', 'c')
('a', 'c')
('a', 'd')
# 1 a transition, 2 b transitions, 6 c transitions, 5 d transitions
如果可能的话，我不想重新实现整个排序，但我不确定这个想法是否可以用 python 的排序“关键函数”来实现。
但是在手动解决问题之后，感觉我可以遵循启发式来获得一个好的解决方案：
看来您首先需要“锁定”集合的范围，方法是首先最小化第一个字段的转换量。所以首先你将列表细分（由 # 表示的细分）列表分为 'a' 和没有
('b',)
()
('b', 'c', 'd')
('b', 'c')
('b', 'd')
('c', 'd')
('d',)
#
('a', 'b', 'd')
('a', 'd')
('a', 'b', 'c', 'd')
('a', 'c')
('a', 'b', 'c')
以后您只能在它们的范围内移动这些元素。然后你继续'b'并将这些范围进一步细分为有和没有两个，但现在它需要“没有b，有b，有b没有b”以完全减少过渡
()
('c', 'd')
('d',)
#
('b',)
('b', 'c', 'd')
('b', 'c')
('b', 'd')
#
('a', 'b', 'd')
('a', 'b', 'c', 'd')
('a', 'b', 'c')
#
('a', 'd')
('a', 'c')
然后是 c，进一步翻转每个部分没有 c 的 c
()
('d',)
#
('c', 'd')
#
('b', 'c', 'd')
('b', 'c')
#
('b',)
('b', 'd')
#
('a', 'b', 'd')
#
('a', 'b', 'c', 'd')
('a', 'b', 'c')
#
('a', 'c')
#
('a', 'd')
最后是 'd'，但这里有点不同，因为我们认为我们只是交换我们正在细分的每个细分的 with/without 的顺序。但在某些时候，您可能不想具体地遵循这一点，例如上面的第三个细分。如果我们稍微打破规则，我们会在这里得到一个完全最优的解决方案：
()
#
('d',)
#
('c', 'd')
#
('b', 'c', 'd')
#
('b', 'c')
#
('b',)
#
('b', 'd')
#
('a', 'b', 'd')
#
('a', 'b', 'c', 'd')
#
('a', 'b', 'c')
#
('a', 'c')
#
('a', 'd')
选择不交换该细分中的 with/without 排序可以降低总成本排序。因此，从本质上讲，在决定当前细分的 with/without 顺序时，您似乎需要匹配前一组对当前元素的包含。这部分让我觉得递归并不是解决问题的好方法。但是，我不确定目前是否可以将这些思想和规则完全表述为python动态规划算法。
您的问题简化为 single-source shortest path problem on an undirected graph with natural number weights, which is addressed by Thorup, 1999, and is solvable in O(E) time. Alternatively, if your state transition costs are not natural numbers, then it is addressed by Fredman & Tarjan, 1984 并且可以在 O(E + Vlog(V)) 时间内解决。
想象一下将此集合中的每个对象布置为图形上的一个顶点。例如，如果您有三个 'states' (x_1, x_2, x_3)，那么您有八个由幂集表示的基础配置：
()
(x_3)
(x_2)
(x_1)
(x_2, x_3)
(x_1, x_3)
(x_1, x_2)
(x_1, x_2, x_3)
这八种配置代表图形上的节点。想象一下，将图形限制为转换成本 1。然后您将得到以下配置：
() -> (x_1) (x_2) (x_3)
(x_1) -> (x_1, x_2) (x_1, x_3), ()
(x_2) -> (x_1, x_2) (x_2, x_3), ()
(x_3) -> ...
在这种情况下，您要优化的是遍历此配置中每个顶点的最短路径。这是您在此处提出的问题的简化版本。
为了完成这个问题，想象一下这种情况的完整图表，K_3。在此配置下，您可以根据切换每个状态的相对困难来分配边权重。例如，如果 (x_1, x_2, x_3) 按增加的难度排序，这样 x_2 和 x_3 永远不会覆盖 x_1 上的转换，则按 2 的幂分配：x_1 成本为 4，x_2 成本为 2，x_3 成本为 1，从而产生正确的顺序。当有多个状态要转换时如何分配成本是一种设计选择，取决于您的问题中未共享的实现细节。
为了适应已经涵盖的配置，您可以像上面那样简单地将它们从幂集中删除，并且re-run剩余顶点的最短路径解决方案。
看来我能够实现我上面描述的贪心动态规划算法，它对我的目的有效。我不会说这是问题的最佳解决方案，也不确定时间复杂度（O(m^2*n) 也许吧？其中 m 是字段数，n 是要订购的集合数）。但与将解决方案映射到图论问题相比，它的实施认知负担更小。
from itertools import chain, combinations
import random
def powerset(iterable):
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
def flatten(to_flatten):
for x in to_flatten:
if hasattr(x, '__iter__') and not isinstance(x, str) and not isinstance(x, tuple):
for y in flatten(x):
yield y
else:
yield x
# order a list of tuples such that the transition between elements is minimized
# prioritizing elements in the order of field_order
def minimize_transitions(tuple_list, field_order):
tuple_lists = [tuple_list]
# whether the field is included last (true), or not included last (false), in the previous list
for field in field_order:
next_tuple_lists = []
ending_with = False
for tuple_list in tuple_lists:
if len(tuple_list) == 1:
ending_with = field in tuple_list[0]
next_tuple_lists.append(tuple_list)
elif len(tuple_list) == 0:
continue
else:
if ending_with:
next_tuple_lists.append(list(filter(lambda this_tuple: field in this_tuple, tuple_list)))
next_tuple_lists.append(list(filter(lambda this_tuple: field not in this_tuple, tuple_list)))
else:
next_tuple_lists.append(list(filter(lambda this_tuple: field not in this_tuple, tuple_list)))
next_tuple_lists.append(list(filter(lambda this_tuple: field in this_tuple, tuple_list)))
ending_with = not ending_with
tuple_lists = next_tuple_lists
return flatten(tuple_lists)
# fields ordered by decreasing difficulty to swap
field_order = ['a', 'b', 'c', 'd', 'e']
field_powerset = list(powerset(field_order))
field_powerset = random.sample(field_powerset, random.randrange(len(field_powerset)))
print("Starting sets:")
[print(subset) for subset in field_powerset]
print()
print("Ordering for minimized transitions:")
field_powerset = minimize_transitions(field_powerset, field_order)
[print(subset) for subset in field_powerset]
Starting sets:
('a', 'c', 'e')
('d', 'e')
('c', 'e')
('a', 'c', 'd')
('a', 'b', 'd', 'e')
('c', 'd', 'e')
('b', 'c', 'd', 'e')
('b', 'd')
('a', 'b', 'c', 'd', 'e')
('a', 'c', 'd', 'e')
('a', 'b', 'd')
('e',)
('a', 'b', 'c')
()
('a', 'b', 'c', 'e')
('a', 'b', 'c', 'd')
('a', 'b', 'e')
('d',)
Ordering for minimized transitions:
()
('e',)
('d', 'e')
('d',)
('c', 'd', 'e')
('c', 'e')
('b', 'c', 'd', 'e')
('b', 'd')
('a', 'b', 'd')
('a', 'b', 'd', 'e')
('a', 'b', 'e')
('a', 'b', 'c', 'e')
('a', 'b', 'c')
('a', 'b', 'c', 'd')
('a', 'b', 'c', 'd', 'e')
('a', 'c', 'd', 'e')
('a', 'c', 'd')
('a', 'c', 'e')