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

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 *拍手

下面是这个问题的输入

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: