使用算法混合七个玩具上的颜色。

Question

我是一名木匠，想在这里寻求数学和算法方面的帮助。

我正在尝试制作28套七巧板，就像这样：

^{DanielHolth + RobotE at nl:Wp [CC BY-SA 3.0 (http://creativecommons.org/licenses/by-sa/3.0/)], from Wikimedia Commons}

这个玩具由7块应该被涂成不同颜色的木板组成。为了使涂漆更容易，我认为最好的方法是将它们分成4组相同颜色的批次进行涂漆，然后混合它们。

我已经标记了这些木块，从1到7，以便讨论更容易:

最有效的方法是什么，可以混合这些木块，使得每个组合的颜色不相同？我希望礼物尽可能的个性化，而颜色组合是实现这一目标的好方法。

编辑：每套七巧板由七块不同颜色的木块组成。

- Tianhe Hou

---

我在我的答案中添加了另一个求解器，它具有更多的随机分配，并且还允许调整分配给我们希望最小化匹配的特定对的权重（第二个代码片段中前几行）。当我试验时，其中一个结果似乎碰撞特别少；我在最后加入了它。 - גלעד ברקן

Answer 1

以某种方式（例如 R -> G -> B -> Y -> P -> O -> W）对颜色进行排序，然后类似地对碎片进行排序（您已经在图片中完成了1-7）。以矩阵形式摆放它们，每种颜色占据一行（重复列/碎片，因为每种颜色将有4个重复）。让 B3 表示蓝色 3 碎片，O7 表示橙色 7，等等。

     1  2  3  4  5  6  7   1  2  3  4  5  6  7   1  2  3  4  5  6  7   1  2  3  4  5  6  7  
(R)  R1 R2 R3 R4 R5 R6 R7  R1 R2 R3 R4 R5 R6 R7  R1 R2 R3 R4 R5 R6 R7  R1 R2 R3 R4 R5 R6 R7
(G)  G1 G2 G3 G4 G5 G6 G7  G1 G2 G3 G4 G5 G6 G7  G1 G2 G3 G4 G5 G6 G7  G1 G2 G3 G4 G5 G6 G7
(G)  B1 B2 B3 B4 B5 B6 B7  B1 B2 B3 B4 B5 B6 B7  B1 B2 B3 B4 B5 B6 B7  B1 B2 B3 B4 B5 B6 B7
(Y)  Y1 Y2 Y3 Y4 Y5 Y6 Y7  Y1 Y2 Y3 Y4 Y5 Y6 Y7  Y1 Y2 Y3 Y4 Y5 Y6 Y7  Y1 Y2 Y3 Y4 Y5 Y6 Y7
(P)  P1 P2 P3 P4 P5 P6 P7  P1 P2 P3 P4 P5 P6 P7  P1 P2 P3 P4 P5 P6 P7  P1 P2 P3 P4 P5 P6 P7
(O)  O1 O2 O3 O4 O5 O6 O7  O1 O2 O3 O4 O5 O6 O7  O1 O2 O3 O4 O5 O6 O7  O1 O2 O3 O4 O5 O6 O7
(W)  W1 W2 W3 W4 W5 W6 W7  W1 W2 W3 W4 W5 W6 W7  W1 W2 W3 W4 W5 W6 W7  W1 W2 W3 W4 W5 W6 W7

现在，请取出左下角的“三角形”块。也就是从第一行的开头删除0块，从第二行删除1块，从第三行删除2块...

     1  2  3  4  5  6  7   1  2  3  4  5  6  7   1  2  3  4  5  6  7   1  2  3  4  5  6  7  
(R)  R1 R2 R3 R4 R5 R6 R7  R1 R2 R3 R4 R5 R6 R7  R1 R2 R3 R4 R5 R6 R7  R1 R2 R3 R4 R5 R6 R7
(G)     G2 G3 G4 G5 G6 G7  G1 G2 G3 G4 G5 G6 G7  G1 G2 G3 G4 G5 G6 G7  G1 G2 G3 G4 G5 G6 G7
(B)        B3 B4 B5 B6 B7  B1 B2 B3 B4 B5 B6 B7  B1 B2 B3 B4 B5 B6 B7  B1 B2 B3 B4 B5 B6 B7
(Y)           Y4 Y5 Y6 Y7  Y1 Y2 Y3 Y4 Y5 Y6 Y7  Y1 Y2 Y3 Y4 Y5 Y6 Y7  Y1 Y2 Y3 Y4 Y5 Y6 Y7
(P)              P5 P6 P7  P1 P2 P3 P4 P5 P6 P7  P1 P2 P3 P4 P5 P6 P7  P1 P2 P3 P4 P5 P6 P7
(O)                 O6 O7  O1 O2 O3 O4 O5 O6 O7  O1 O2 O3 O4 O5 O6 O7  O1 O2 O3 O4 O5 O6 O7
(W)                    W7  W1 W2 W3 W4 W5 W6 W7  W1 W2 W3 W4 W5 W6 W7  W1 W2 W3 W4 W5 W6 W7

然后将这些额外的元素放在它们对应行的末尾。现在，只需从每一行中取第一个元素，并创建一个新集合。在此之前，您可以这样做7次，然后它就会重复。为了清晰起见，在上面的示例中，您的第一个集合将是 R1 G2 B3 Y4 P5 O6 W7，第二个集合将是 R2 G3 B4 Y5 P6 O7 W1。

之后，再次重复这个过程 - 从第一行中删除0，从第二行中删除1等等。再次将额外的元素移至其行的末尾，并从每行的第一个元素中绘制7个新集合。针对最后两批各有7组，重复此过程两次。每个集合都是独特的。

- Dillon Davis

---

这太聪明了，我喜欢它！而且它足够简单，在车间里执行。谢谢你，谢谢你。 - Tianhe Hou

请注意，此模式会重复颜色序列。（我并不是说这有什么不好，只是想指出。） - גלעד ברקן

Answer 2

为了好玩，这里有一些代码尝试最小化在相同位置中可以存在的连续颜色对的数量，以响应你对“尽可能独特”的要求，但并没有进行详尽的搜索。它具有一定的随机性。有时会产生三个序列的重复，但在最好的情况下，我们只会得到成对的重复。（也许接收者之间发现的相似之处是美丽的一部分。）

（Dillon Davis指出，它可能会为位置1和5或4和6生成相同的对，这在设计中似乎是突出的相似三角形。稍后我可能会对其进行更改，以优先避免这些重复。）

let cs = ['R', 'G', 'B', 'Y', 'P', 'O', 'W'];

let pairs = [];

for (let i=0; i<6; i++)
  for (let j=i+1; j<7; j++)
    pairs.push(cs[i] + cs[j], cs[j] + cs[i]);

let positionMatches = [];
const results = pairs.slice(0, 28);

// Build combinations
for (let i=0; i<5; i++){
  // Avoid repeating pairs
  // in the same position
  let set = new Set();

  for (let j=0; j<28; j++){
    const last = results[j].substr(-1);
    let found = false;

    for (let c of cs){
      const candidate = last + c;

      // Match found
      if (!set.has(candidate) && !results[j].includes(c)){
        results[j] += c;
        set.add(candidate);
        found = true;
        break;
      }
    }
    // Match not found
    // Lower the restriction
    // and insert random match
    if (!found){
      const cs_ = cs.filter(
        c => !results[j].includes(c));
      const c = cs_[
        ~~(Math.random()*cs_.length)];
      results[j] += c;
      positionMatches.push((i+2) + ':' + last + c);
    }
  }
}

console.log(results.join('\n'));

console.log('');

for (let p of positionMatches){
  const [pos, pair] = p.split(':');
  console.log(pair + ' duplicate at position ' + pos)
}

更新

这里有一个比上面的解决方案更加随机的求解器，因此更加不可预测。我们可以在unmatch映射中设置我们想要“取消匹配”的配对，并且控制我们希望在检查特别选择的未匹配对或其他对时尝试多少更多的随机候选者（我们可能希望给前者更多权重以让它们尝试更多的随机候选者）。我在玩耍时得到了一个看起来相当不错的结果（使用相同的50/50随机设置）。单击“运行片段”每次都会得到不同的结果！

const unmatch = {
  // Try to avoid duplicate pairs
  // at indexes (0, 4) and (3, 5)
  4: 0,
  5: 3
};
const unmatchTrials = 50;
const regularTrials = 50;

let cs = ['R', 'G', 'B', 'Y', 'P', 'O', 'W'];
let pairs = [];

for (let i=0; i<6; i++)
  for (let j=i+1; j<7; j++)
    pairs.push(cs[i] + cs[j], cs[j] + cs[i]);

let positionMatches = [];
const results = pairs.slice(0, 28);

// Build combinations
for (let i=0; i<5; i++){
  // Avoid repeating pairs in the same position,
  // as well as in custom positions
  let set = new Set();
  let unmatchS = new Set();

  for (let j=0; j<28; j++){
    const last = results[j].substr(-1);
    let found = false;
    const ri = i + 2;
    let count = unmatch.hasOwnProperty(ri) ? unmatchTrials : regularTrials;

    while (!found && --count > 0){
      const ii = ~~(Math.random() * cs.length);
      const c = cs[ii];
      const candidate = last + c;
      let u = unmatch.hasOwnProperty(ri)
      ? unmatchS.has(results[j][unmatch[ri]] + c)
      : false;

      // Match found
      if (!set.has(candidate) && !results[j].includes(c) && !u){
        results[j] += c;
        set.add(candidate);
        if (unmatch.hasOwnProperty(ri))
          unmatchS.add(results[j][unmatch[ri]] + c)
        found = true;
      }
    }
    // Match not found
    // Lower the restriction
    // and insert random match
    if (!found){
      const cs_ = cs.filter(
        c => !results[j].includes(c));
      const c = cs_[
        ~~(Math.random()*cs_.length)];
      results[j] += c;
      positionMatches.push((i+2) + ':' + last + c);
    }
  }
}

console.log(results.join('\n'));

console.log('');

for (let p of positionMatches){
  const [pos, pair] = p.split(':');
  console.log(pair + ' duplicate at position ' + pos)
}

let m04 = new Set();
let m35 = new Set();

for (let r of results){
  const c04 = r[0] + r[4];
  const c35 = r[3] + r[5];
  if (m04.has(c04))
    console.log('15 match: ' + c04);
  m04.add(c04);
  if (m35.has(c35))
    console.log('46 match: ' + c35);
  m35.add(c35);
}

下面的输出似乎很不错。 Dillon Davis注意到有一对七巧板，它们共享序列“POW”。这可能是为两个人准备的，他们可能已经知道或尚不知道彼此之间有特殊的联系。（当然，我们也可以手动调整其中一个 :)

RGWBYOP
GROBPYW
RBPWOYG
BRWYOGP
RYWPGOB
YRPBGWO
RPBYWOG
PRYGWBO
ROBWPGY
ORGYPBW
RWGOBYP
WRBOPGY
GBOWYRP
BGOYRWP
GYRWBPO
YGROWPB
GPWORBY
PGYBRWO
GOYPWRB
OGPYBRW
GWPROBY
WGBRYPO
BYGPOWR
YBRPOWG
BPGRWYO
PBYWGOR
BORGPWY
OBWGRPY

PO duplicate at position 4
PG duplicate at position 5
RW duplicate at position 5
OW duplicate at position 5
GO duplicate at position 5
GY duplicate at position 6
WO duplicate at position 6
BY duplicate at position 6
PO duplicate at position 6
46 match: BW
15 match: BO
46 match: PW

- גלעד ברקן

---

我注意到这段代码运行在一个限制内。这段代码是否会使用拼图28个部分中的所有部分？如果是，我可以将相同颜色的部分对齐在一起，并按照代码建议用手拿出来拼图。 - Tianhe Hou

@TianheHou 请注意，尽管这种方法试图最小化共存的颜色对，但它似乎没有考虑到1和5号以及4和6号方块是相同的事实，因此这些方块将不可避免地创建意外/未计算的颜色对。 - Dillon Davis

@TianheHou，一些（1,5）或（4,6）对的可能重复似乎足以引起对代码进行更改的关注吗？请告诉我，我会看看是否可以防止这种情况。 - גלעד ברקן

我已经发布了自己的替代方案，试图解决这些更棘手的重复问题，但我的算法速度较慢，并且不能保证任何两个集合之间的总重复次数最少，只能保证上限为2个重复项。也许你能在其中找到一些有用的东西来帮助修复你的问题。 - Dillon Davis

@DillonDavis 这些是给可能还不知道他们之间有特殊联系的两个人准备的。（也可以手动调整其中一个 :) - גלעד ברקן

Answer 3

我已经发布了一个尽可能简单的解决方案来解决这个问题，但我认为提供一个旨在最大化独特性的解决方案也是合适的。另一个答案已经涵盖了基础知识，但没有考虑由相同的拼图块创建的颜色对，因此我在这里尝试解决这个问题。

这个求解器不是最快的，但保证任何两个集合之间不会有超过两个颜色相同的拼图块。如果不进行洗牌，就会有一种颜色占据特定的拼图块的偏见，因此我提供了一个参数来对中间数组进行洗牌，以消除这种偏见，代价是生成的集合较少（可能小于28-如果是这样，请再次运行）。程序将输出满足上述条件的所有找到的集合，因此您可以手动选择最符合人眼“随机”或“均匀”的28个集合。

from itertools import combinations, permutations
from random import shuffle

def get_subsets(color_set):
    subsets = []
    for d in ({}, {'1':'5'}, {'4':'6'}, {'1':'5', '4':'6'}):
        tr = lambda s: str.translate(s, str.maketrans(d))
        subsets.extend(set(tr(y) for y in x) for x in combinations(color_set, 3))
    return subsets

def make_sets(do_random=True):
    color_sets = [set(c+str(i) for i, c in enumerate(perm)) for perm in permutations("RGBYPOW")]

    results, pairs = [], []
    while color_sets:
        results.append(color_sets[0])
        pairs.extend(get_subsets(color_sets[0]))
        color_sets = [x for x in color_sets if all(y - x for y in pairs)]
        if do_random: shuffle(color_sets)

    results = sorted(sorted(perm, key=lambda x:x[1]) for perm in results)
    print("\n".join(map(str, results)))
    print(len(results))

if __name__ == "__main__":
    make_sets()

示例输出：

['B0', 'G1', 'O2', 'W3', 'P4', 'R5', 'Y6']
['B0', 'P1', 'W2', 'Y3', 'O4', 'G5', 'R6']
['B0', 'R1', 'W2', 'O3', 'G4', 'P5', 'Y6']
['B0', 'R1', 'Y2', 'P3', 'W4', 'O5', 'G6']
['B0', 'W1', 'R2', 'G3', 'O4', 'Y5', 'P6']
['G0', 'B1', 'O2', 'P3', 'R4', 'W5', 'Y6']
['G0', 'B1', 'R2', 'W3', 'Y4', 'O5', 'P6']
['G0', 'O1', 'P2', 'B3', 'W4', 'R5', 'Y6']
['G0', 'O1', 'Y2', 'R3', 'B4', 'W5', 'P6']
['G0', 'P1', 'O2', 'Y3', 'B4', 'R5', 'W6']
['G0', 'W1', 'P2', 'O3', 'R4', 'Y5', 'B6']
['O0', 'B1', 'Y2', 'W3', 'R4', 'P5', 'G6']
['O0', 'G1', 'R2', 'Y3', 'W4', 'P5', 'B6']
['O0', 'P1', 'G2', 'R3', 'Y4', 'B5', 'W6']
['O0', 'R1', 'B2', 'G3', 'P4', 'W5', 'Y6']
['P0', 'B1', 'R2', 'O3', 'W4', 'Y5', 'G6']
['P0', 'R1', 'G2', 'W3', 'B4', 'Y5', 'O6']
['P0', 'W1', 'B2', 'Y3', 'O4', 'R5', 'G6']
['P0', 'W1', 'G2', 'B3', 'Y4', 'O5', 'R6']
['R0', 'G1', 'B2', 'Y3', 'P4', 'O5', 'W6']
['R0', 'O1', 'P2', 'Y3', 'G4', 'W5', 'B6']
['R0', 'Y1', 'W2', 'P3', 'G4', 'B5', 'O6']
['W0', 'G1', 'B2', 'P3', 'R4', 'Y5', 'O6']
['W0', 'O1', 'P2', 'G3', 'Y4', 'B5', 'R6']
['W0', 'R1', 'Y2', 'G3', 'O4', 'P5', 'B6']
['W0', 'Y1', 'G2', 'O3', 'B4', 'P5', 'R6']
['W0', 'Y1', 'O2', 'R3', 'P4', 'G5', 'B6']
['Y0', 'B1', 'P2', 'R3', 'W4', 'G5', 'O6']
['Y0', 'G1', 'W2', 'O3', 'B4', 'R5', 'P6']
['Y0', 'O1', 'B2', 'G3', 'R4', 'P5', 'W6']
['Y0', 'P1', 'R2', 'B3', 'G4', 'W5', 'O6']
31

- Dillon Davis

---

我在我的答案中添加了另一个求解器，它具有更多的随机分配（也可以进行微调）。其中一个结果看起来相当不错，所以我也包括了它（它只有两个4,6匹配和一个1,5匹配，并且相对较少的连续对匹配）。 - גלעד ברקן