Как математически описать перебор кода из 7 цифр?

Question

[Евгений Плотников]

Приветствую!
Есть код из 7 цифр от 1 до 4 (1, 2, 3, 4)
Необходимо составить массив с возможными комбинациями.
При этом в комбинации должно быть как минимум 2 цифры и они должны повторяться как минимум дважды.
Начала массива для наглядности:

$array = [[2, 2, 1, 1, 1, 1, 1],
          [2, 1, 2, 1, 1, 1, 1],
          [2, 1, 1, 2, 1, 1, 1]];

Ни как не могу математически описать данное действие. Поделитесь решением или ссылкой на математическое решение.

Comments

[Deerenaros]

Непонятно, что значит должно быть как минимум 2 цифры и они должны повторяться как минимум дважды.
А вообще, . Конечно, это не априори самая верный способ записи. При чтении надо держать в уме, что двоеточие читается, как "такой(ие), что", "Е наоборот" - "существует", "А наоборот" - "для всех (любых)", "Э наоборот" - принадлежит.

Answer 1

[DaNHell]

Download File Gen

Примерно такого как я понял, на ночь глядя конечно не с генерирую метод, и его определение. Но если никто не предложит, как грится, тряхну стариной.. матаном)

--------
UPD: Нашел пример на php. Немного переделал под задачу, может ошибся где, PHPшники думаю увидят сразу если что-то не так.

char abc[] = new char[]{'1','2','3','4'};//множество допустимых символов
int size = 7;//кол-во элементов
int arr[] = new int[size];//массив для хранения текущего варианта множества
outer: while(true){//вечный цикл
 
	//вывод варианта множества на экран
	for(int ndx : arr){
		System.out.print(abc[ndx]);
	}
	System.out.println();
 
	int i = size - 1;//ставим курсов в самую правую ячейку
	while(arr[i] == abc.length - 1){//движемся влево, если ячейка переполнена
		arr[i] = 0;//записываем в ячейку 0, т.к. идет перенос разряда
		i--;//сдвиг влево
		//если перенос влево невозможен, значит перебор закончен
		if(i < 0)break outer;
	}
	arr[i]++;//увеличиваем значение ячейки на единицу
}

Comments

[Евгений Плотников]

да примерно такое надо, но на пхп или математически:)

[DaNHell]

Евгений Evgenx: )) либо я совсем сплю либо тут подвох.
смысл попробую объяснить.
Генерируем массив со всеми возможными.
А затем просто исключаем:
1. Избавляемся от первого условия (как минимум 2 цифры) - просто удаляем
"1111111","2222222",333333"","44444444"
2. Ну от второго условия чуть посложнее.

Или совсем бред несу, проснусь почитаю )

[Евгений Плотников]

DaNHell: хорошо, а как его сгенерировать?

[DaNHell]

Евгений Evgenx: дали на всех языках кроме php) могу на питоне показать как)
Но я видел пример на php, через пол часика постараюсь найти

[DaNHell]

Евгений Evgenx: ну а исключить уже сортировкой, думаю найти пример можно даже в офф. документации

Answer 2

[Александр Ручкин]

На хаскелях отвечу

codes = [c |
    c <- replicateM 7 [1..4],
    length (nub $ sort c) >= 2, -- как минимум 2 цифры используется
    all ((>= 2) . length) $ group $ sort c] -- каждой цифры минимум 2 штуки

Answer 3

[Mrrl]

"как минимум 2 цифры и они должны повторяться как минимум дважды"
Если разных цифр ровно две, то ясно, что имеется в виду. А если больше? Скажем, годится ли код 1122234, в котором две цифры повторяются не менее двух раз, но две другие - нет?

Боюсь, что годится только прямой перебор. На C это бы выглядело так:

char s[8],stat[4];
  int i,j,k;
  s[7]='\0';
  for(i=0;i<16384;i++){
     k=i;
     for(j=0;j<4;j++) stat[j]=0;
     for(j=0;j<7;j++){
        stat[k%4]++;
        s[j]=(char)((k%4)+'1');
        k/=4;
    }
    if((stat[0]>=2)+(stat[1]>=2)+(stat[2]>=2)+(stat[3]>=2)>=2) printf("%s\n",s);
  }

Код не проверялся.

Comments

[Евгений Плотников]

да

Answer 4

[Антон Меньшов]

Если отвечать с теоретической точки зрения, то следующий подход может быть субоптимальный:
1) сгенерировать все возможные сочетания цифр (1,2,3,4) из 7 элементов с повторениями (честно говоря, не до конца понял, есть ли ограничение в вашей задаче на количество повторений).
2) Для каждого из сочетаний применить Алгоритм Нарайаны (https://ru.wikipedia.org/wiki/Алгоритм_Нарайаны) для генерации перестановок.