11111100
00000010
00000001
Нужен алгоритм
Добрый день всем... нужен алгоритм, реализующий перестановки. Задача следующая:
есть n коробок и m объектов. нужен алгоритм, позволяющий разместить всеми возможными способами объекты в коробках, каждый раз в корбке должен быть как минимум 1 объект. Объекты нумерованные и их порядок в коробках важен.
Пример: 2 коробки А и В, 3 объекта 1,2 и 3. необходим алгоритм, позволяющий получить следующие решения:
А - 1, В - 2,3
А - 1, В - 3,2
А - 1,2 В - 3
А - 2,1 В - 3
А - 1,3 В - 2
А - 3,1 В - 2
А - 2, В - 1,3
А - 2, В - 3,1
А - 2,3 В - 1
А - 3,2 В - 1
А - 3 В - 1,2
А - 3 В - 2,1
Алгоритм нужен срочно. Спасибо заранее. Вобщем, все возможные перестановки найти надо. Условие, что по одному объекту в коробке можно снять, т.к. оно легко проверяется.
есть n коробок и m объектов. нужен алгоритм, позволяющий разместить всеми возможными способами объекты в коробках, каждый раз в корбке должен быть как минимум 1 объект. Объекты нумерованные и их порядок в коробках важен.
Пример: 2 коробки А и В, 3 объекта 1,2 и 3. необходим алгоритм, позволяющий получить следующие решения:
А - 1, В - 2,3
А - 1, В - 3,2
А - 1,2 В - 3
А - 2,1 В - 3
А - 1,3 В - 2
А - 3,1 В - 2
А - 2, В - 1,3
А - 2, В - 3,1
А - 2,3 В - 1
А - 3,2 В - 1
А - 3 В - 1,2
А - 3 В - 2,1
Алгоритм нужен срочно. Спасибо заранее. Вобщем, все возможные перестановки найти надо. Условие, что по одному объекту в коробке можно снять, т.к. оно легко проверяется.
Цитата:
Originally posted by xelos
Добрый день всем... нужен алгоритм, реализующий перестановки. Задача следующая:
есть n коробок и m объектов. нужен алгоритм, позволяющий разместить всеми возможными способами объекты в коробках, каждый раз в корбке должен быть как минимум 1 объект.
Пример: 2 коробки А и В, 3 объекта 1,2 и 3. необходим алгоритм, позволяющий получить следующие решения:
А - 1, В -2,3
А - 1,2 В - 3
А - 1,3 В - 2
А - 2, В -1,3
А - 2,3 В - 1
А - 3 В - 1,2
Алгоритм нужен срочно. Спасибо заранее.
Добрый день всем... нужен алгоритм, реализующий перестановки. Задача следующая:
есть n коробок и m объектов. нужен алгоритм, позволяющий разместить всеми возможными способами объекты в коробках, каждый раз в корбке должен быть как минимум 1 объект.
Пример: 2 коробки А и В, 3 объекта 1,2 и 3. необходим алгоритм, позволяющий получить следующие решения:
А - 1, В -2,3
А - 1,2 В - 3
А - 1,3 В - 2
А - 2, В -1,3
А - 2,3 В - 1
А - 3 В - 1,2
Алгоритм нужен срочно. Спасибо заранее.
Я тут посмотрел, подумал...
Самый простой способ - перебор.
1. Создаёшь массив логических элементов размерностью количество коробок Х количество объектов
2. Задаёшь логическую переменную, например А
3. Заполняешь коробки в 1 исходный вариант так, чтобы у тебя в 1 коробке было максимум элементов. Например:
Код:
Я бы это делал в цикле вида:
Код:
For i=0 to m-n
b(0,i) = True
next
A = i
For D = I to M
FOR C=1 TO N
IF D>A THEN
B(D,C) = True
A = D
ENDIF
NEXT
NEXT
b(0,i) = True
next
A = i
For D = I to M
FOR C=1 TO N
IF D>A THEN
B(D,C) = True
A = D
ENDIF
NEXT
NEXT
Вроде нигде не обшибся.
Потом начинай "осыпать" в циклах значение из "верхнего" массива в нижние, чтобы получались матрицы вида
Код:
11111000
00000110
00000001
11110000
00001110
00000001
11100000
00011110
00000001
00000110
00000001
11110000
00001110
00000001
11100000
00011110
00000001
ну и так далее.
Теперь так. Строка матрицы - это логическое сложение
Логически складываешь элементы строк и перемножаешь. Если в итоге - True, то выводишь матрицу в качестве варианта ответа, иначе ищешь следующий вариант.
забыл уточнить, объекты нумерованные и порядок объектов в коробках важен.
12345
67
и
12345
76
различнные решения.
потом при выводе результата, каждое решение нужно вывести на экран один раз.
см. корректировку условия
12345
67
и
12345
76
различнные решения.
потом при выводе результата, каждое решение нужно вывести на экран один раз.
см. корректировку условия
я тут тоже подумал, по идее эту задачу можно разбить на две отдельные задачи из комбинаторики:
первая, если есть n объектов - найти все возможные перестановки объектов.
задача 2 - найти все возможные способы размещения n объектов в m коробках без учета порядка...
т.о. сначала делаем алгоритм 2, а потом для каждой коробки алгоритм 1.
первая, если есть n объектов - найти все возможные перестановки объектов.
задача 2 - найти все возможные способы размещения n объектов в m коробках без учета порядка...
т.о. сначала делаем алгоритм 2, а потом для каждой коробки алгоритм 1.
Цитата:
Originally posted by xelos
я тут тоже подумал, по идее эту задачу можно разбить на две отдельные задачи из комбинаторики:
первая, если есть n объектов - найти все возможные перестановки объектов.
задача 2 - найти все возможные способы размещения n объектов в m коробках без учета порядка...
т.о. сначала делаем алгоритм 2, а потом для каждой коробки алгоритм 1.
я тут тоже подумал, по идее эту задачу можно разбить на две отдельные задачи из комбинаторики:
первая, если есть n объектов - найти все возможные перестановки объектов.
задача 2 - найти все возможные способы размещения n объектов в m коробках без учета порядка...
т.о. сначала делаем алгоритм 2, а потом для каждой коробки алгоритм 1.
все, решил...
для раскидки объектов по ящикам делаем следующую вещь :
берем число длиной в количество объектов с базой в количество ящиков и организуем счетчик. Т.е. пусть есть ящики А,В,С и 4 объекта. Записываем число
АААА потом увеличиваем на 1 за каждый проход число:
АААВ
АААС
ААВА
ААВВ
и т.д.
это означает, что для АСАВ
в ящике А объекты 1,3, в ящике В - объект 4, в ящике С объект 2.
теперь перестановки - пусть в ящике n объектов, тогда число всех перестановок будет n!
начинаем с самого маленького числа.
алгоритм начинается с последней цифры и идет к первой. смотрим с конца числа неубывающую подпоследовательность. как дошли до первого числа этой подпоследовательности, меняем его и стоящее перед ним местами. образовавшуюся последовательность записываем в возрастающем порядке. начинаем по новой с самого последнего числа.
Насчет перестановок идеей помог один друг математик :):) доказательство этого алгоритма оставляю всем желающим в качестве упражнения :):)