Комбинаторика - как получить все возможные варианты?

@Veseliy Hakker · Регистрация: 23.01.2018

Всем привет! Есть задача. Даны четыре буквы A B C D. Всего можно получить 24 варианта смешения этих букв, так как
4! = 24. Я выяснил, что:
Должны получиться следующие варианты:
ABCD BACD CABD DABC
ABDC BADC CADB DACB
ACBD BCAD CBAD DBAC
ACDB BCDA CBDA DBCA
ADCB BDCA CDAB DCAB
ADBC BDAC CDBA DCBA

И что можно разбить все варианты на пары:
2 AB 2 BA
2 BC 2 CB
2 AC 2 CA
2 AD 2 DA
2 BD 2 DB
2 CD 2 DC

Задача многократно упростилась. Как совместить эти пары? Например, AB нужно подобрать нужные варианты. Повторений букв быть не должно, а значит подходит только пара CD, которая не содержит ни A, ни B. То есть из всех шести пар подходит только одна и ее зеркальное отображение. Давно ломаю голову над этой задачей, пожалуйста помогите решить )

HighPredator · 26.07.2019, 08:03

Java

public class Main {
    public static void main(String[] args) {
        Permutator<Character> permutator = new Permutator<>(new Character[]{'A', 'B', 'C', 'D'});
 
        while (permutator.hasNext())
            System.out.println(Arrays.deepToString(permutator.next()));
    }
}

Класс Permutator возьмите здесь: Комбинаторика с использованием PermutationIterator

@Veseliy Hakker · 27.07.2019, 18:32 **[ТС]**

HighPredator, Интересное решение. Я тут прикинул, а что если подключить это дело к базе данных? То есть вместо букв вводить строковые переменные или числовые и потом генерировать из них варианты? Затем, при помощи задачи коммивояжера, выбирать наиболее оптимальные варианты из того что есть? Генетический алгоритм для решения коммивояжера есть. И потом, при вводе 10 вариантов (букв), выводится только 33 728 вариантов, хотя факториал 10 равен 3 628 800... Как это исправить? Если не затруднит, можно это с вами обсудить? Спасибо за ответ.

PS Факториал шести выдает исправно 720 вариантов )

HighPredator · 29.07.2019, 09:57

Veseliy Hakker, вообще ничего не понял

@Veseliy Hakker · 29.07.2019, 13:32 **[ТС]**

HighPredator, При вводе 10 вариантов (букв), выводится только 33 728 вариантов, хотя факториал 10 равен 3 628 800... Как это исправить? Я так понимаю, проблема в типе данных. С типа int нужно как-то переписать на long? Или же проблема в самом hashMap()?

HighPredator · 29.07.2019, 14:09

Сообщение от Veseliy Hakker

выводится только 33 728 вариантов

В консоль? Так там лимит стоит.

@Veseliy Hakker · 01.08.2019, 19:31 **[ТС]**

HighPredator, Записывает в файл и в бд, работает гуд, спасибо ) Сейчас балуюсь разными вариантами)

@Veseliy Hakker 0 / 1 / 0 Регистрация: 23.01.2018 Сообщений: 72
		1
	Комбинаторика - как получить все возможные варианты? 25.07.2019, 19:02. Просмотров 2307. Ответов 6 Метки комбинаторика, массивы, факториал, циклы (Все метки) Всем привет! Есть задача. Даны четыре буквы A B C D. Всего можно получить 24 варианта смешения этих букв, так как 4! = 24. Я выяснил, что: Должны получиться следующие варианты: ABCD BACD CABD DABC ABDC BADC CADB DACB ACBD BCAD CBAD DBAC ACDB BCDA CBDA DBCA ADCB BDCA CDAB DCAB ADBC BDAC CDBA DCBA И что можно разбить все варианты на пары: 2 AB 2 BA 2 BC 2 CB 2 AC 2 CA 2 AD 2 DA 2 BD 2 DB 2 CD 2 DC Задача многократно упростилась. Как совместить эти пары? Например, AB нужно подобрать нужные варианты. Повторений букв быть не должно, а значит подходит только пара CD, которая не содержит ни A, ни B. То есть из всех шести пар подходит только одна и ее зеркальное отображение. Давно ломаю голову над этой задачей, пожалуйста помогите решить ) 0

@Veseliy Hakker 0 / 1 / 0 Регистрация: 23.01.2018 Сообщений: 72
	27.07.2019, 18:32 [ТС]	3
	HighPredator, Интересное решение. Я тут прикинул, а что если подключить это дело к базе данных? То есть вместо букв вводить строковые переменные или числовые и потом генерировать из них варианты? Затем, при помощи задачи коммивояжера, выбирать наиболее оптимальные варианты из того что есть? Генетический алгоритм для решения коммивояжера есть. И потом, при вводе 10 вариантов (букв), выводится только 33 728 вариантов, хотя факториал 10 равен 3 628 800... Как это исправить? Если не затруднит, можно это с вами обсудить? Спасибо за ответ. PS Факториал шести выдает исправно 720 вариантов ) 0

HighPredator 5980 / 2106 / 737 Регистрация: 10.12.2010 Сообщений: 5,923 Записей в блоге: 3
	29.07.2019, 09:57	4
	Veseliy Hakker, вообще ничего не понял 0

@Veseliy Hakker 0 / 1 / 0 Регистрация: 23.01.2018 Сообщений: 72
	29.07.2019, 13:32 [ТС]	5
	HighPredator, При вводе 10 вариантов (букв), выводится только 33 728 вариантов, хотя факториал 10 равен 3 628 800... Как это исправить? Я так понимаю, проблема в типе данных. С типа int нужно как-то переписать на long? Или же проблема в самом hashMap()? 0

HighPredator 5980 / 2106 / 737 Регистрация: 10.12.2010 Сообщений: 5,923 Записей в блоге: 3
	29.07.2019, 14:09	6
	Сообщение от Veseliy Hakker выводится только 33 728 вариантов В консоль? Так там лимит стоит. 1

@Veseliy Hakker 0 / 1 / 0 Регистрация: 23.01.2018 Сообщений: 72
	01.08.2019, 19:31 [ТС]	7
	HighPredator, Записывает в файл и в бд, работает гуд, спасибо ) Сейчас балуюсь разными вариантами) 0

Опции темы

Комбинаторика - как получить все возможные варианты?

Решение