算法对7个个人的玩具碎片混合颜色

Question

我想在这里寻求专业知识的一些数学和算法帮助一个木工。

我试图让28套七巧板馈赠亲友，像这样：

DanielHolth + RobotE在NL：WP [CC BY-SA 3.0（http://creativecommons.org/licenses/by-sa/3.0/)]，来自维基共享资源

该玩具共有7个木板应涂上各种颜色。为了使绘画更容易，我认为最好的办法就是画他们的4套批次相同的颜色，然后将它们混合。

我已经标记了个1-7，以使讨论更容易：

什么是碎片混，所以我不明白每个组相同的颜色组合的最有效方法是什么？我想礼物尽可能从个人和色彩组合是实现这一目标的好方法。

编辑：每套拼图是由各个不同颜色的七个部分。

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

现在，拿出作品的左下角“三角”。这是 - 从所述第二，2从第三除去从第一行，1的开头0 ...件

     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。

在此之后，重复该过程再次 - 从第一行，1从第二等除去0同样，移动额外到其行的两端，并且从每行的所述第一要素绘制7件新套。重复此过程，两次为每个7套你的最后两批。每组将是独一无二的。

Answer 2

我已经张贴，试图尽可能简单地解决问题的答案，但我认为这是适当的，以提供一个解决方案，同时试图最大化的唯一性。另一个答案已经涵盖的这个基础，但不考虑来自同一拼图创建的颜色对，所以我试图所以在这里做。

这求解不是最快的，但保证不会有两个以上相同颜色对任意两个集合之间的作品。当不带改组跑，有对某些颜色服用特定件大的偏差，所以我提供参数洗牌中间阵列以消除这种偏差，以更少的产生集（可能小于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

Answer 3

为了好玩，这里是一些试图最小化，没有一个详尽的搜索代码，可以在同一位置共存，企图顺序颜色对的数量来响应您的要求为“作为单独的越好。”它具有随机性的元素。有时候，它可以产生三重序列重复的，但在它的最好的，我们只能得到一式两份。 （也许有机会相似之处受助人之间找到他们的礼物将是美的一部分。）

（狄龙戴维斯评论说，它可以产生对位置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)
}

UPDATE

下面是与更多的随机分配比上面的一个，这是比较连续的，因此可预见的求解器。我们可以设置对，我们希望“失配”的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);
}

（下面的输出似乎相当不错。狄龙戴维斯注意到一对七巧板的有共享序列“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