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

Приветствую!
Есть код из 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]];

Ни как не могу математически описать данное действие. Поделитесь решением или ссылкой на математическое решение.
  • Вопрос задан
  • 2670 просмотров
Пригласить эксперта
Ответы на вопрос 4
DaNHell
@DaNHell
Change the world
XhvO550.pngDownload 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]++;//увеличиваем значение ячейки на единицу
}
Ответ написан
На хаскелях отвечу

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы