algorithm - 最大化选取元素与集合的距离(避免重复)的算法

Question

我正在寻找一个算法，它成功地将下面的问题推广到n个集合，但是为了简单起见，假设有4个不同的集合，每个集合包含4个元素。我们还可以假设每个集合总是包含相同数量的元素，但是可以有任意数量的元素。所以如果第一个集合中有37个元素，我们可以假设其他集合中也有37个元素。
元素的组合是从第一个集合中取一个元素放在第一位，从第二个集合中取一个元素放在第二位，以此类推。例如，第一组包含{a0，a1，a2，a3}，第二组包含{b0，b1，b2，b3}，第三组是{c0，c1，c2，c3}，第四组是{d0，d1，d2，d3}。一种可能的组合是[a0，b2，c1，d3]。
我们的目标是找到路径最大化的距离时，循环通过所有可能的组合，避免重复尽可能多。避免重复适用于相邻的组和单个列。例如：
单个列
[a0，b0，c0，d0]
[A1、B1、C1、D1]
[A2、B0、C2、D2]
这是不正确的，因为b0的重复比必须的要快。
邻接群
[a0，b0，c0，d0]
[A1、B1、C1、D1]
[A2、B2、C2、D2]
[A3、B3、C3、D3]
[a0、b0、c1、d2]
这是不正确的，因为相邻对（a0，b0）重复得比必须重复得快。但是如果最后一个是[a0，b1，c0，d1]，那么这就可以了。
当循环通过所有可能的组合时，必须重复相邻的组，但目标是最大化它们之间的距离。例如，如果使用（a0，b0），那么理想情况下，在再次使用之前，将使用所有其他第一对。
当有3个集合时，我能找到一个解，但是我很难将它推广到n个集合，甚至不能求解4个集合。有什么想法吗？
你能把你的三套解决方案贴出来吗？
当然，首先我写下所有可能的组合。然后，我通过将非连续（第一个和第三个）元素重复的条目分组，生成了三个3x3的条目矩阵：

(A0,B0,C0)1, (A1,B0,C1)4, (A2,B0,C2)7    (A0,B0,C1)13, (A1,B0,C2)16, (A2,B0,C0)10    (A0,B0,C2)25, (A1,B0,C0)19, (A2,B0,C1)22
(A0,B1,C0)8, (A1,B1,C1)2, (A2,B1,C2)5    (A0,B1,C1)11, (A1,B1,C2)14, (A2,B1,C0)17    (A0,B1,C2)23, (A1,B1,C0)26, (A2,B1,C1)20
(A0,B2,C0)6, (A1,B2,C1)9, (A2,B2,C2)3    (A0,B2,C1)18, (A1,B2,C2)12, (A2,B2,C0)15    (A0,B2,C2)21, (A1,B2,C0)24, (A2,B2,C1)27

Then I realized if I traversed in a diagonal pattern (order indicated by the superscript index) that it would obey the rules. I then wrote the following code to take advantage of this visual pattern:

@Test
public void run() {

    List<String> A = new ArrayList<String>();
    A.add("0");
    A.add("1");
    A.add("2");
    List<String> B = new ArrayList<String>();
    B.add("0");
    B.add("1");
    B.add("2");
    List<String> C = new ArrayList<String>();
    C.add("0");
    C.add("1");
    C.add("2");

    int numElements = A.size();

    List<String> output = new ArrayList<String>();

    int offset = 0;
    int nextOffset = 0;

    for (int i = 0; i < A.size()*B.size()*C.size(); i++) {

        int j = i % numElements;
        int k = i / numElements;

        if (j == 0 && k%numElements == numElements-1) {
            nextOffset = (j+k+offset) % numElements;
        }

        if (j == 0 && k%numElements == 0) {
            offset = nextOffset;
        }

        String first = A.get((j+k+offset) % numElements);
        String second = B.get(j);
        String third = C.get((j+k) % numElements);

        System.out.println(first + " " + second + " " + third);
        output.add(first + second + third);
    }

}

不过，我刚刚意识到，这也不理想，因为在指数8和11处，这对组合（a0，b1）似乎重复得太快了：（然而，我认为，当从一个组切换到另一个组时，这可能是不可避免的？……这是个难题！比看上去更难
如果你能考虑并修改你的实际要求
好的，所以我决定取消遍历所有可能的组合的限制，而是减少一点输出，以提高结果的质量。
这一点的全部目的是获取属于特定集合的元素，并将它们组合在一起，形成看起来独特的元素组合。所以如果我从3个组合开始，有3个集合，我可以将每个组合分解成3个元素，并将这些元素放入各自的集合中。然后我可以使用算法来混合和匹配元素，并生成27个看似唯一的组合——当然，它们是由派生元素构成的，所以只要你不看得太近，它们才会显得唯一！
因此，手工形成的3个组合可以变成33个组合，节省了大量的时间和精力。当然这也可以很好地扩展，如果我手工形成10个组合，那么算法可以生成1000个组合。我可能不需要太多的组合，所以我可以牺牲一些条目，以更好地避免重复。尤其是3组，我注意到虽然我的解决方案是体面的，但每个numelements2条目都发生了一些聚集。下面是一个由3组5个元素组成的示例，在25个组合之后有明显的重复：
19）A1 B3 C1
20）A2 B4 C2
21）A4 b0 C4<--
22）a0 b1 c0
23）A1 B2 C1
24）A2 B3 C2
25）A3 B4 C3
26）a0 b0 c4级<--
27）A1 B1二氧化碳
28）A2 B2 C1
29）A3 B3 C2型
30）A4 B4 C3
31）A1 b0二氧化碳
32）A2 B1 C1
为了解决这个问题，我们可以引入以下语句并去掉这个坏块：

if (k % numElements == 0) continue;

但是，这仅在numElements>numSets时有效，否则将破坏单个列规则。（如果你想知道，在这个例子中我也改变了第一组和第三组的顺序，那么我开始是这样做的，这样我就不会以错误的重复开始了）
我仍然完全被困在如何形成一个N集甚至4集的方法上。它当然变得更加棘手，因为现在有不同大小的相邻组要避免，相邻的三人组以及成对的。有什么想法吗？我真的为自己的努力而疯狂吗？

Answer 1

即使你的问题做了修改，我还是不确定你到底想要什么。看来你真正想要的是不可能的，但我不确定在这种条件下究竟有多少放松是可以接受的。不过，我还是要试一试。
奇怪的是，似乎很少有文献（无论如何，我都能找到）涉及到你的问题，所以我不得不自己发明一些东西。这是一个想法：你正在寻找一个多维环面上的点序列，使得序列中的元素在一个复杂的度量中尽可能远离。这让我想起了几年前在力学课上学到的东西，奇怪的是。如果你有一条直线在一个具有有理斜率的平面环面上，那么这条直线会在几个周期后回到自身，但是如果你有一条具有有理斜率的直线，那么这条直线将密集地覆盖整个环面。
我不认为这对很多人意味着什么，但它确实给了我一个主意。每一组的索引可能会有一个不合理的数量。当然，你必须先发言，然后再进行模块化，但可以说，它似乎很好地覆盖了基础。每个集合的非理性步骤可能是不同的（使用相当松散的语言来说，是相互非理性的）。
为了使这个想法更精确，我写了一个简短的程序。请检查一下。

class Equidistributed {
  static final double IRRATIONAL1 = Math.sqrt(2);
  static final double IRRATIONAL2 = Math.sqrt(3);
  static final double IRRATIONAL3 = Math.sqrt(5)-1;

  // four sets of 7 elements each
  static int setSize = 7;

  public static void main(String[] args) {
    for (int i = 0; i < Math.pow(setSize,4); i++) {
      String tuple = "";
      int j = i % setSize;
      tuple += j + ",";
      j = ((int)Math.floor(i*IRRATIONAL1)) % setSize;
      tuple += j + ",";
      j = ((int)Math.floor(i*IRRATIONAL2)) % setSize;
      tuple += j + ",";
      j = ((int)Math.floor(i*IRRATIONAL3)) % setSize;
      tuple += j;
      System.out.println(tuple);
    }
  }
}

我“目测”了一下结果，结果并不完美，但相当不错。而且程序运行得很快。这是四个元素数目可变的集合（我在示例中选择了7）。我使用的无理数是基于素数的平方根；我从sqrt（5）中减去了1，所以结果在1和2之间。每个元组基本上是

(i, floor(i*irrational1), floor(i*irrational2), floor(i*irrational3)) mod 7

从统计学上讲，这会使序列均匀分布，这是你想要的结果。这是否能转化为正确的“距离”属性，我不能确定。您可能应该编写一个程序来测试序列是否具有所需的属性，然后将来自我的程序的输出管道化到测试中。