Форум программистов, компьютерный форум, киберфорум
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.64/11: Рейтинг темы: голосов - 11, средняя оценка - 4.64
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
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.07.2019, 19:02
Ответы с готовыми решениями:

Комбинаторика: вывести все возможные комбинации заданных объектов
Добрый день, может кто-нибудь,пожалуйста, написать код для следующей задачи? Поскольку в...

Программа должна предложить все возможные варианты распределения учеников по классам.
Всем привет! Записался на курсы по Java. Прошли if - esle и switch. Вот задача: Есть 5 классов с х...

Рекурсия: вывести все возможные варианты расположения элементов массива без повторов
Доброго времени суток.Объясните пожалуйста в чем ошибка.Есть массив,нужно что бы программа вывела...

Комбинаторика: вывести все возможные варианты
Вывести все возможные варианты слов, которые можно составить из первых 4-х букв английского...

6
5980 / 2106 / 737
Регистрация: 10.12.2010
Сообщений: 5,923
Записей в блоге: 3
26.07.2019, 08:03 2
Лучший ответ Сообщение было отмечено Veseliy Hakker как решение

Решение

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

PS Факториал шести выдает исправно 720 вариантов )
0
5980 / 2106 / 737
Регистрация: 10.12.2010
Сообщений: 5,923
Записей в блоге: 3
29.07.2019, 09:57 4
Veseliy Hakker, вообще ничего не понял
0
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
5980 / 2106 / 737
Регистрация: 10.12.2010
Сообщений: 5,923
Записей в блоге: 3
29.07.2019, 14:09 6
Цитата Сообщение от Veseliy Hakker Посмотреть сообщение
выводится только 33 728 вариантов
В консоль? Так там лимит стоит.
1
0 / 1 / 0
Регистрация: 23.01.2018
Сообщений: 72
01.08.2019, 19:31  [ТС] 7
HighPredator, Записывает в файл и в бд, работает гуд, спасибо ) Сейчас балуюсь разными вариантами)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.08.2019, 19:31

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Перебрать все возможные варианты расположения заполненных ячеек (комбинаторика)
Есть 12 парных элементов, это значит что каждый элемент имеет две ячейки (всего 24 ячейки...

Комбинаторика. вывести на экран все возможные варианты товара на основании характеристик
Ребята, помогите с реализацией, немогу вдуплить ... Суть задачи в том что на основании различных...

Получить все возможные варианты загрузки ящиков
На перевозку 800 кг овощей с базы подготовлены ящики. В них можно загрузить по 8, 10 и 15...

Получить все возможные варианты расположения букв
Нужно сделать так чтобы пользователь мог ввести слово и получить все возможные варианты...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.