Алгоритм смешивания цветов на 7 отдельных игрушках

Question

Я - столяр, пытаюсь получить помощь по математике и алгоритмам, чтобы получить опыт здесь.

Я пытаюсь сделать 28 комплектов Tangram для подарков родственникам, например:

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

Игрушки состоят из 7 деревянных досок, которые должны быть окрашены в индивидуальные цвета. Я думаю, что для облегчения рисования лучше всего покрасить их в партии по 4 набора в один цвет, а затем смешать их.

Я обозначил кусочки 1-7, чтобы облегчить обсуждение:

Какой самый эффективный способ смешать кусочки, чтобы я неполучить одинаковую комбинацию цветов в каждом наборе? Мне бы хотелось, чтобы подарок был как можно более индивидуальным, а сочетание цветов - хороший способ достижения этой цели.

Редактировать: каждый набор головоломки состоит из семи частей каждого изразного цвета.

Answer 1

Для забавы, вот некоторый код, который пытается минимизировать, без исчерпывающего поиска, количество последовательных пар цветов, которые могут сосуществовать в одной и той же позиции, пытаясь ответить на ваш запрос "как можно более индивидуально".Это элемент случайности.Иногда он может создать дубликат тройной последовательности, но в лучшем случае мы получаем только пару дубликатов.(Может быть, шанс, что получатели получат сходство между своими подарками, станет частью красоты.)

(Диллон Дэвис отметил, что он может производить идентичные пары для позиций 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);
}

(Вывод, показанный ниже, казался довольно хорошим. Диллон Дэвис заметил там пару танграмм, которые разделяют последовательность «военнопленных». Это могут быть два человека, которые могут или могутеще не знаю, что они имеют особую связь. (Вы могли бы, вы знаете, просто настроить одну из них вручную :)

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

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

Закажите ваши цвета некоторым способом (скажем, 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 комплектов в каждой.Каждый набор будет уникальным.