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

@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
1
2
3
4
5
6
7
8
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, Записывает в файл и в бд, работает гуд, спасибо ) Сейчас балуюсь разными вариантами)

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .

@Veseliy Hakker 0 / 1 / 0 Регистрация: 23.01.2018 Сообщений: 148

	Комбинаторика - как получить все возможные варианты? 25.07.2019, 19:02. Показов 4564. Ответов 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 Сообщений: 148
	27.07.2019, 18:32 [ТС]
	HighPredator, Интересное решение. Я тут прикинул, а что если подключить это дело к базе данных? То есть вместо букв вводить строковые переменные или числовые и потом генерировать из них варианты? Затем, при помощи задачи коммивояжера, выбирать наиболее оптимальные варианты из того что есть? Генетический алгоритм для решения коммивояжера есть. И потом, при вводе 10 вариантов (букв), выводится только 33 728 вариантов, хотя факториал 10 равен 3 628 800... Как это исправить? Если не затруднит, можно это с вами обсудить? Спасибо за ответ. PS Факториал шести выдает исправно 720 вариантов ) 0

HighPredator 6045 / 2160 / 753 Регистрация: 10.12.2010 Сообщений: 6,005 Записей в блоге: 3
	29.07.2019, 09:57
	Veseliy Hakker, вообще ничего не понял 0

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

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

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

Решение