如何合并两个列表以找到最小重复因子？

Question

例如，我有两个列表

A = ["spin", "dab", "dab", "moonwalk", "clap", "moonwalk"]
B = ["dab", "dab", "spin", "clap", "clap", "moonwalk"]

合并两个列表后，我可以得到这样的列表

remix=["dab", "spin", "dab", "spin", "dab", "clap", "dab", "moonwalk", "clap", "moonwalk", "clap", "moonwalk"]

我的问题是如何合并两个列表，使相邻元素的重复最少（A和B中的所有元素必须出现在混合列表中）。 重复是这样的

remix=["spin", "dab", "spin", "dab", "dab", "clap", "dab", "moonwalk", "clap", "moonwalk", "clap", "moonwalk"]

这里相邻的重复是2*dab

另一个例子是

remix=["spin", "dab", "spin", "dab", "dab", "clap", "clap","dab", "moonwalk", "moonwalk", "clap", "moonwalk"]

相邻的重复是2*dab+2*clap

下面是这个问题的输入

A = ["spin", "dab", "dab", "moonwalk", "clap", "moonwalk"]
B = ["dab", "dab", "spin", "clap", "clap", "moonwalk"]
factor={"spin":1,"dab":2,"moonwalk":3,"clap":4}

输出列表：

["dab", "spin", "dab", "spin", "dab", "clap", "dab", "moonwalk", "clap", "moonwalk", "clap", "moonwalk"]

原因是没有重复，因此任何元素的相邻重复都是0。 同样，我们的目标是找到相邻重复最少的列表，当然，如果我们能找到一个完全没有重复的列表，那么因子可以是0

我在考虑动态规划，但我不知道如何使它工作。感谢您的帮助。你知道吗

Answer 1

我不太确定你的预期产出。你是说这样的事吗？你知道吗

import random
A = ["spin", "dab", "dab", "moonwalk", "clap", "moonwalk"]
B = ["dab", "dab", "spin", "clap", "clap", "moonwalk"]

AB = A + B
elem = AB
while elem != []:
    random.shuffle(AB)
    elem = []
    for i in range(len(AB)-1):
        if AB[i] == AB[i+1]:
            elem.append([AB[i],AB[i+1]])
    print (AB)
    print (elem)
    print ("Repetition factor: ")
    for e in elem:
        print(str(len(e)) + "*" + e[0])
    print ("\n")

输出：

['spin', 'moonwalk', 'dab', 'dab', 'spin', 'dab', 'moonwalk', 'moonwalk', 'clap', 'clap', 'dab', 'clap']
[['dab', 'dab'], ['moonwalk', 'moonwalk'], ['clap', 'clap']]
Repetition factor: 
2*dab
2*moonwalk
2*clap

['spin', 'dab', 'clap', 'dab', 'moonwalk', 'dab', 'dab', 'clap', 'moonwalk', 'clap', 'moonwalk', 'spin']
[['dab', 'dab']]
Repetition factor: 
2*dab

['moonwalk', 'dab', 'clap', 'moonwalk', 'clap', 'dab', 'spin', 'dab', 'moonwalk', 'clap', 'dab', 'spin']
[]
Repetition factor: