Комбинации: числа от 1 до 22, итого 4 числа неповторяющиеся

Question

Если у нас есть лотерея с номерами от 1 до 22 в пуле. Мы должны нарисовать четыре числа. Общее количество комбинаций из 4 чисел составляет 7 315.

Теперь сложная часть, предположим, что вы хотите сохранить комбинации, в которых не более 2 из 4 одинаковы.

Например, вы рисуете комбинацию 1,2,3,4, тогда 1,2,3,5 или 2,3,4,6 не годятся. Следующая действительная комбинация - 1,2,5,6, потому что никакие три числа не являются такими же, как в 1,2,3,4.

Как я могу вытащить все комбинации с 1,2,3,4 до 19,20,21,22, которые имеют только два одинаковых числа из всех других комбинаций.

Или по какой формуле можно узнать, сколько существует допустимых комбинаций?

Вот несколько первых действительных комбинаций. (1,2,3,4) :( 1,2-5,6) :( 1,2,7,8) :( 1,2,9,10) :( 1,2,11,12): (1,2,13,14) ...

Спасибо за любую помощь заранее, DJ

Answer 1

Вот довольно не элегантный метод грубой силы.

#!/usr/bin/python

from sets import Set

setlist = []

# Generate all sets
# Sets are guaranteed to have only unique numbers
# Note: Python ranges are inclusive on the left but exclusive on the right
for first in range(1,23):
  for second in range(first+1,23):
    for third in range(second+1,23):
      for fourth in range(third+1,23):
        possible = Set([first, second, third, fourth])
        # Only take sets of 4 digits
        if len(possible) == 4:
          setlist.append(possible)

# Print the total number of combinations
print len(setlist)

answers = []
for aset in setlist:
  # Append the first answer automatically
  if len(answers) == 0:
     answers.append(aset)

  ok = True
  #Check against all our previous answers
  for answer in answers:
    # We have more than two intersecting values, this is not an answer
    if (len(answer.intersection(aset)) > 2):
      ok = False
      break;

  # If our answer is ok
  if ok:
    answers.append(aset)

# Clean up our answers and sort them all
clean = []
for answer in answers:
  temp = list(answer)
  temp.sort()
  clean.append(temp)
# Print the clean answers
print clean


# Print the total
print len(answers)

Answer 2

То, что вы ищете, называется комбинаторным блочным дизайном.Количество элементов в базовом наборе равно 22, а количество элементов в каждом блоке равно 4. Кроме того, у блоков должно быть свойство, чтобы триплет (например, {1,2,3}) не появлялся более чем в одном блоке., что является более точным способом сказать: «Вы хотите сохранить только комбинации, в которых только 2 из 4 одинаковы».

Чтобы получить верхнюю границу для количества блоков, сначала рассмотрим один блок (например, {1,2,3,4}).В этом блоке четыре тройки: {1,2,3}, {1,2,4}, {1,3,4} и {2,3,4}.Общее количество троек из 22 элементов составляет _{22 * ​​1004 * C 3 = 22x21x20 / (3x2x1) = 1540. Поскольку каждый блок содержит 4 тройки, максимальное количество блоков составляет 1540/4 =385. Это не значит, что можно найти 385 блоков, но мы увидим через мгновение.}

Обратите внимание, что создание дизайна «жадным» методом, как пытался другой плакат, почти навернякаобречен на провал.Выбор на ранней стадии в жадном алгоритме отрицательно повлияет на число вариантов позже, что, вероятно, приведет к тупику до того, как будет найдено 385 блоков.

Если вы найдете схему блока, где встречается каждая тройка ровно один раз, а не раз, вы нашли 3- (22,4,1) блочную конструкцию.3 - для троек, 22 - количество базовых элементов, 4 - размер блоков, и 1 - количество раз, когда встречается каждая тройка.Такая конструкция блока также известна как четырехместная система Штейнера.

Была проведена некоторая академическая работа над четырехместными системами Штейнера.В частности, Ханани Х. «О четырехместных системах».КанадскийJ. Math.12, 145-157, 1960 показано, что четырехкратная система возможна тогда и только тогда, когда число элементов соответствует 2 или 4 мод 6. Поскольку 22 соответствует 4 мод. 6, в вашем случае существует четырехкратная система, поэтомуможно найти полный набор из 385 блоков.

В статье Ханани также приводится явная конструкция, которая слишком сложна, чтобы описывать ее здесь, но, к счастью, была реализована в системе FOSS Sage.Вы можете скачать Sage бесплатно и просто запустить print designs.steiner_quadruple_system(22), чтобы получить список из 385 блоков.Обратите внимание, что нумерация начинается с 0, поэтому, если вы хотите, чтобы ваши номера были от 1 до 22, просто добавьте 1 к каждому номеру, и если вам нужен блок с четырьмя последовательными номерами, отличными от {1,2,3,4}, вы можете задатьдля перенумерации (или просто сделайте это самостоятельно, добавив k mod 22 к каждому числу в дизайне).

Вот блоки, поставленные Sage:

blocks=[[0, 1, 2, 3], [0, 1, 4, 5],
[0, 1, 6, 21], [0, 1, 7, 8], [0, 1, 9, 17], [0, 1, 10, 16], [0, 1, 11,
19], [0, 1, 12, 18], [0, 1, 13, 20], [0, 1, 14, 15], [0, 2, 4, 6], [0,
2, 5, 21], [0, 2, 7, 9], [0, 2, 8, 17], [0, 2, 10, 15], [0, 2, 11, 20],
[0, 2, 12, 19], [0, 2, 13, 18], [0, 2, 14, 16], [0, 3, 4, 21], [0, 3, 5,
6], [0, 3, 7, 10], [0, 3, 8, 16], [0, 3, 9, 15], [0, 3, 11, 18], [0, 3,
12, 20], [0, 3, 13, 19], [0, 3, 14, 17], [0, 4, 7, 11], [0, 4, 8, 19],
[0, 4, 9, 20], [0, 4, 10, 17], [0, 4, 12, 15], [0, 4, 13, 16], [0, 4,
14, 18], [0, 5, 7, 12], [0, 5, 8, 18], [0, 5, 9, 16], [0, 5, 10, 20],
[0, 5, 11, 15], [0, 5, 13, 17], [0, 5, 14, 19], [0, 6, 7, 13], [0, 6, 8,
15], [0, 6, 9, 18], [0, 6, 10, 19], [0, 6, 11, 16], [0, 6, 12, 17], [0,
6, 14, 20], [0, 7, 14, 21], [0, 7, 15, 20], [0, 7, 16, 19], [0, 7, 17,
18], [0, 8, 9, 10], [0, 8, 11, 12], [0, 8, 13, 14], [0, 8, 20, 21], [0,
9, 11, 13], [0, 9, 12, 14], [0, 9, 19, 21], [0, 10, 11, 14], [0, 10, 12,
13], [0, 10, 18, 21], [0, 11, 17, 21], [0, 12, 16, 21], [0, 13, 15, 21],
[0, 15, 16, 17], [0, 15, 18, 19], [0, 16, 18, 20], [0, 17, 19, 20], [1,
2, 4, 21], [1, 2, 5, 6], [1, 2, 7, 17], [1, 2, 8, 9], [1, 2, 10, 14],
[1, 2, 11, 18], [1, 2, 12, 20], [1, 2, 13, 19], [1, 2, 15, 16], [1, 3,
4, 6], [1, 3, 5, 21], [1, 3, 7, 16], [1, 3, 8, 10], [1, 3, 9, 14], [1,
3, 11, 20], [1, 3, 12, 19], [1, 3, 13, 18], [1, 3, 15, 17], [1, 4, 7,
19], [1, 4, 8, 11], [1, 4, 9, 16], [1, 4, 10, 20], [1, 4, 12, 14], [1,
4, 13, 17], [1, 4, 15, 18], [1, 5, 7, 18], [1, 5, 8, 12], [1, 5, 9, 20],
[1, 5, 10, 17], [1, 5, 11, 14], [1, 5, 13, 16], [1, 5, 15, 19], [1, 6,
7, 14], [1, 6, 8, 13], [1, 6, 9, 19], [1, 6, 10, 18], [1, 6, 11, 17],
[1, 6, 12, 16], [1, 6, 15, 20], [1, 7, 9, 10], [1, 7, 11, 12], [1, 7,
13, 15], [1, 7, 20, 21], [1, 8, 14, 20], [1, 8, 15, 21], [1, 8, 16, 18],
[1, 8, 17, 19], [1, 9, 11, 15], [1, 9, 12, 13], [1, 9, 18, 21], [1, 10,
11, 13], [1, 10, 12, 15], [1, 10, 19, 21], [1, 11, 16, 21], [1, 12, 17,
21], [1, 13, 14, 21], [1, 14, 16, 17], [1, 14, 18, 19], [1, 16, 19, 20],
[1, 17, 18, 20], [2, 3, 4, 5], [2, 3, 6, 21], [2, 3, 7, 15], [2, 3, 8,
14], [2, 3, 9, 10], [2, 3, 11, 19], [2, 3, 12, 18], [2, 3, 13, 20], [2,
3, 16, 17], [2, 4, 7, 20], [2, 4, 8, 15], [2, 4, 9, 11], [2, 4, 10, 19],
[2, 4, 12, 17], [2, 4, 13, 14], [2, 4, 16, 18], [2, 5, 7, 14], [2, 5, 8,
20], [2, 5, 9, 12], [2, 5, 10, 18], [2, 5, 11, 17], [2, 5, 13, 15], [2,
5, 16, 19], [2, 6, 7, 18], [2, 6, 8, 19], [2, 6, 9, 13], [2, 6, 10, 17],
[2, 6, 11, 14], [2, 6, 12, 15], [2, 6, 16, 20], [2, 7, 8, 10], [2, 7,
11, 13], [2, 7, 12, 16], [2, 7, 19, 21], [2, 8, 11, 16], [2, 8, 12, 13],
[2, 8, 18, 21], [2, 9, 14, 19], [2, 9, 15, 18], [2, 9, 16, 21], [2, 9,
17, 20], [2, 10, 11, 12], [2, 10, 13, 16], [2, 10, 20, 21], [2, 11, 15,
21], [2, 12, 14, 21], [2, 13, 17, 21], [2, 14, 15, 17], [2, 14, 18, 20],
[2, 15, 19, 20], [2, 17, 18, 19], [3, 4, 7, 14], [3, 4, 8, 20], [3, 4,
9, 19], [3, 4, 10, 11], [3, 4, 12, 16], [3, 4, 13, 15], [3, 4, 17, 18],
[3, 5, 7, 20], [3, 5, 8, 15], [3, 5, 9, 18], [3, 5, 10, 12], [3, 5, 11,
16], [3, 5, 13, 14], [3, 5, 17, 19], [3, 6, 7, 19], [3, 6, 8, 18], [3,
6, 9, 16], [3, 6, 10, 13], [3, 6, 11, 15], [3, 6, 12, 14], [3, 6, 17,
20], [3, 7, 8, 9], [3, 7, 11, 17], [3, 7, 12, 13], [3, 7, 18, 21], [3,
8, 11, 13], [3, 8, 12, 17], [3, 8, 19, 21], [3, 9, 11, 12], [3, 9, 13,
17], [3, 9, 20, 21], [3, 10, 14, 18], [3, 10, 15, 19], [3, 10, 16, 20],
[3, 10, 17, 21], [3, 11, 14, 21], [3, 12, 15, 21], [3, 13, 16, 21], [3,
14, 15, 16], [3, 14, 19, 20], [3, 15, 18, 20], [3, 16, 18, 19], [4, 5,
6, 21], [4, 5, 7, 15], [4, 5, 8, 14], [4, 5, 9, 17], [4, 5, 10, 16], [4,
5, 11, 12], [4, 5, 13, 20], [4, 5, 18, 19], [4, 6, 7, 16], [4, 6, 8,
17], [4, 6, 9, 14], [4, 6, 10, 15], [4, 6, 11, 13], [4, 6, 12, 19], [4,
6, 18, 20], [4, 7, 8, 12], [4, 7, 9, 13], [4, 7, 10, 18], [4, 7, 17,
21], [4, 8, 9, 18], [4, 8, 10, 13], [4, 8, 16, 21], [4, 9, 10, 12], [4,
9, 15, 21], [4, 10, 14, 21], [4, 11, 14, 17], [4, 11, 15, 16], [4, 11,
18, 21], [4, 11, 19, 20], [4, 12, 13, 18], [4, 12, 20, 21], [4, 13, 19,
21], [4, 14, 15, 19], [4, 14, 16, 20], [4, 15, 17, 20], [4, 16, 17, 19],
[5, 6, 7, 17], [5, 6, 8, 16], [5, 6, 9, 15], [5, 6, 10, 14], [5, 6, 11,
18], [5, 6, 12, 13], [5, 6, 19, 20], [5, 7, 8, 11], [5, 7, 9, 19], [5,
7, 10, 13], [5, 7, 16, 21], [5, 8, 9, 13], [5, 8, 10, 19], [5, 8, 17,
21], [5, 9, 10, 11], [5, 9, 14, 21], [5, 10, 15, 21], [5, 11, 13, 19],
[5, 11, 20, 21], [5, 12, 14, 16], [5, 12, 15, 17], [5, 12, 18, 20], [5,
12, 19, 21], [5, 13, 18, 21], [5, 14, 15, 18], [5, 14, 17, 20], [5, 15,
16, 20], [5, 16, 17, 18], [6, 7, 8, 20], [6, 7, 9, 11], [6, 7, 10, 12],
[6, 7, 15, 21], [6, 8, 9, 12], [6, 8, 10, 11], [6, 8, 14, 21], [6, 9,
10, 20], [6, 9, 17, 21], [6, 10, 16, 21], [6, 11, 12, 20], [6, 11, 19,
21], [6, 12, 18, 21], [6, 13, 14, 15], [6, 13, 16, 17], [6, 13, 18, 19],
[6, 13, 20, 21], [6, 14, 16, 18], [6, 14, 17, 19], [6, 15, 16, 19], [6,
15, 17, 18], [7, 8, 13, 21], [7, 8, 14, 15], [7, 8, 16, 17], [7, 8, 18,
19], [7, 9, 12, 21], [7, 9, 14, 16], [7, 9, 15, 17], [7, 9, 18, 20], [7,
10, 11, 21], [7, 10, 14, 17], [7, 10, 15, 16], [7, 10, 19, 20], [7, 11,
14, 18], [7, 11, 15, 19], [7, 11, 16, 20], [7, 12, 14, 19], [7, 12, 15,
18], [7, 12, 17, 20], [7, 13, 14, 20], [7, 13, 16, 18], [7, 13, 17, 19],
[8, 9, 11, 21], [8, 9, 14, 17], [8, 9, 15, 16], [8, 9, 19, 20], [8, 10,
12, 21], [8, 10, 14, 16], [8, 10, 15, 17], [8, 10, 18, 20], [8, 11, 14,
19], [8, 11, 15, 18], [8, 11, 17, 20], [8, 12, 14, 18], [8, 12, 15, 19],
[8, 12, 16, 20], [8, 13, 15, 20], [8, 13, 16, 19], [8, 13, 17, 18], [9,
10, 13, 21], [9, 10, 14, 15], [9, 10, 16, 17], [9, 10, 18, 19], [9, 11,
14, 20], [9, 11, 16, 18], [9, 11, 17, 19], [9, 12, 15, 20], [9, 12, 16,
19], [9, 12, 17, 18], [9, 13, 14, 18], [9, 13, 15, 19], [9, 13, 16, 20],
[10, 11, 15, 20], [10, 11, 16, 19], [10, 11, 17, 18], [10, 12, 14, 20],
[10, 12, 16, 18], [10, 12, 17, 19], [10, 13, 14, 19], [10, 13, 15, 18],
[10, 13, 17, 20], [11, 12, 13, 21], [11, 12, 14, 15], [11, 12, 16, 17],
[11, 12, 18, 19], [11, 13, 14, 16], [11, 13, 15, 17], [11, 13, 18, 20],
[12, 13, 14, 17], [12, 13, 15, 16], [12, 13, 19, 20], [14, 15, 20, 21],
[14, 16, 19, 21], [14, 17, 18, 21], [15, 16, 18, 21], [15, 17, 19, 21],
[16, 17, 20, 21], [18, 19, 20, 21]]