按数据帧中最相似的字符串对所有行和列进行排序

Question

我有一个包含许多列和行的数据框架，完全未排序。我希望对每列中的行进行排序，以便每行中的每个元素都位于所有其他列中最相似的元素旁边。我知道this解决方案，但我希望在多个列表/列之间进行比较，就像排序算法一样

     col1     col2      col3      col4
0    Some     Black     Red       Sky
1    Blue     Green     Floor     Bucket
2    Blacky   Same      Green     Rad

我们考虑第一个字母（第一个2？3？）必须是一个精确的命中。这将导致

     col1     col2      col3      col4
0    Some     Same                Sky       #Some and Same are very similar, Sky is the closest in col4                                 
1    Blue                                   #No match for Blue 
2    Blacky   Black               Bucket    #Black,Blacky are similar, and more similar to Bucket
3             Green     Green               #Exact match
4                       Red       Rad       #Similar Match
5                       Floor               #No word started with F in any other column

为了解决这个问题，我想到了以下两种方法之一：

1. 对于每个列，构建所有其他列中所有元素的唯一列表，并将目标列与共识对齐。但我不确定以后会发生什么
2. 对于每个元素，为每个其他列查找最近的1个元素
3. 简单地按字母顺序排序

以上都有问题，在所有情况下，我都需要做一些手动检查（这很好）

Answer 1

1. 为每个单词分配一个id
2. 预先计算每个单词之间的Levenshtein距离和其他列中的每个单词之间的Levenshtein距离。将结果存储在一个方阵中，由单词的ID索引
3. 将一行的成本定义为该行中所有词对之间距离的总和
4. 现在，您需要为每个单词分配一行，以最小化所有行的成本之和，同时遵守同一列中的单词必须位于不同行的约束。这个优化问题是一个二次分配问题，可以很容易地传递给二次整数规划库

在步骤1中，当标识IDS时，IDS必须是唯一的，因此考虑所有单词不同。两个词是否相同并不重要；无论如何，给他们不同的身份证

在步骤2中，您需要在与同一列中的成对单词对应的单元格中输入一些默认值；你选择的值并不重要

在步骤4中，可以将约束改写为“每列中每行仅出现一次”，这是一个简单的线性约束