对列表列表进行排序以对字符进行分组并最小化邻接变化

Question

我有一个问题，我需要对包含任意数量字符（“A”、“B”和“C”）的列表列表进行排序。每个内部列表可以有不同的长度，范围从一个字符到最多十个字符。我的目标是以最小化邻接更改次数的方式对列表列表进行排序。换句话说，尽可能地对扁平化列表进行分组。

例如，给定输入列表：

[["A"],["B", "A", "A"],["B", "C", "B"],["C", "A"]]

扁平化版本是

[A, B, A, A, B, C, B, C, A]

从左到右阅读字符变化 7 次。

在这种情况下，所需的输出将是：

[["A"],["A", "A", "B"],["B", "B", "C"],["C", "A"]]

从左到右阅读时字符只改变 3 次。

我可以更改列表出现的顺序（我在示例中没有这样做），以及每个列表中的单独顺序。但是，我不允许将字符放在各自列表之外。目标是在展平 2D 阵列时最小化更改次数。

我试图通过贪婪地选择下一个列表来解决这个问题，导致最少的字符更改并以固定方式对该列表进行排序。然而，这在效率和结果上表现不佳

任何人都可以提出一种有效解决这个问题的算法或方法吗？我将不胜感激对这个问题的任何见解。谢谢！