Вход | Регистрация


Информационные технологии :: Математика и алгоритмы

Перебор цифр в массиве

Перебор цифр в массиве
Я
   Nikoss
 
16.01.13 - 15:01
В общем есть произвольной длины массив содержащий только 0 и 1.
к примеру: 0001001101101

мне нужно перебрать все возможные варианты расстановки 0 и единиц, кол-во единиц задается...

подскажите... :(
 
 
   НафНаф
 
1 - 16.01.13 - 15:02
контрольная?
   НафНаф
 
2 - 16.01.13 - 15:02
если длина реально произвольная, то вариантов бесконечно
   Nikoss
 
3 - 16.01.13 - 15:04
да нет, в том то и прикол, что школу и университет давно окончил%) "произвольная" имеется в виду - указывается...
т.е. длина к примеру 22, кол-во единиц 5
   NS
 
4 - 16.01.13 - 15:04
Нужен перебор, или нужно рассчитать количество комбинаций?
   Nikoss
 
5 - 16.01.13 - 15:05
именно перебор, кол-во комбинаций не проблема посчитать
   drcrasher
 
6 - 16.01.13 - 15:09
банально:
- строка 0000 (заданная длина)
- если кол-во 1  фиксированно (т.е. строго n "1", а на от 0 до n), то подстановкой 00001111. Дальше перебор в виде 00010111, 00011011, 00011101...
- если не фиксировано, то см выше, но с учетом ввода новых 1-чек

позиции хранить в массиве, например.
   NS
 
7 - 16.01.13 - 15:10
Процедура перебор_рек(стр,колед,длин)  
   Если длин=0 Тогда
       сообщить(стр);
       возврат;
   КонецЕсли;
   Для  а=?(колед=длин,1,0) по ?(колед=0,0,1) Цикл
        перебор_рек(стр+а,колед-а,длин-1);
   КонецЦикла;
КонецПроцедуры    
Процедура Перебор(количество_единиц,Длина_числа);
   Перебор_рек("",количество_единиц,Длина_числа);
КонецПроцедуры    
Процедура Сформировать()
    Перебор(2,5);
КонецПроцедуры
   1Сергей
 
8 - 16.01.13 - 15:22
(7) ниасилел
   DimGan
 
9 - 16.01.13 - 15:24
)))
п1 расчитываем количество комбинаций
п2 смотрим какое число в 10ричной сист принадлежит всем нулям
п3 смотрим какое число принадлежит всем еденицам
п4 перебираем десятичные числа от первой до последней переводя каждый раз в двоичную систему.
   NS
 
10 - 16.01.13 - 15:25
Элементарный код. Если количество отавшихся единиц равно нулю, то цикл с нуля до нуля, если число оставшихся единиц равно числу оставшихся цифр - то цикл с единицы до единицы. Иначе цикл от 0 до 1. Для каждого знака.
 
 Рекламное место пустует
   1Сергей
 
11 - 16.01.13 - 15:28
(10) а... умно
   Nikoss
 
12 - 16.01.13 - 15:37
(7) спасибо.

только на 30/6 уже загнулся

можно как то, чтобы примерно 50/10 осилил в минут 10?

или это самый оптимальный вариант?
   NS
 
13 - 16.01.13 - 15:42
(12) Загибается на выводе?
Я не смогу уменьшить количество возможных перестановок :)
   1Сергей
 
14 - 16.01.13 - 15:44
видимо, быстрее будет, если делать не на 1С
   acsent
 
15 - 16.01.13 - 15:46
50/10 - это сколько перестановок?
   NS
 
16 - 16.01.13 - 15:53
(14) Быстрее что? Перебор на порядки быстрее вывода на экран.
И обработать квадрилионы сочетаний естественно не получится ни на каком компе, и бстродействие не поможет.
(15) Много. Не сосчитает. Солнце помешает - землю поглатит через несколько миллиардов лет.
   Nikoss
 
17 - 16.01.13 - 15:55
10 272 278 170
всего та

(16) да вывод отключал конечно
   NS
 
18 - 16.01.13 - 15:57
(17) Вроде ты неправильно сосчитал.
   NS
 
19 - 16.01.13 - 15:58
50!/40!/10!
   NS
 
20 - 16.01.13 - 15:59
Нет, всё верно. Но всё-равно многовато.
Сейчас ускорю.
   NS
 
21 - 16.01.13 - 16:00
Хотя некуда ускорять :(
   SUA
 
22 - 16.01.13 - 16:00
10^9 считает за разумное время, здесь 10^10
с полчаса-2часа думать будет
   1Сергей
 
23 - 16.01.13 - 16:01
50/* = 1 125 899 906 842 624 вариантов
   acsent
 
24 - 16.01.13 - 16:03
можно без рекурсии обойтись
http://symmetrica.net/algorithms/combinations.htm
   NS
 
25 - 16.01.13 - 16:04
(24) Конечно можно. Только быстрее не будет. Основное время потратится на обработку набора, а не на перебор.
   NS
 
26 - 16.01.13 - 16:05
Любая рекурсия заменяется стеком.
   acsent
 
27 - 16.01.13 - 16:05
(25) набор не хранить в памяти писать последовательно в текст
   NS
 
28 - 16.01.13 - 16:07
(27) Ничего не понял.
   acsent
 
29 - 16.01.13 - 16:11
(28) тогда поясни что ты имел ввиду под обработкой набора?
   NS
 
30 - 16.01.13 - 16:17
(29) Ему не просто нужно перебрать все перестановки,
а что-то с ними нужно сделать. Каждую с чем-то сравнить.
Перестановки у меня не сохраняются в памяти и так. А просто перебор их последовательно получает.
   Nikoss
 
31 - 17.01.13 - 10:00
Вообще задача состоит в следующем:
Есть, грубо, таблица: Номенклатура, Сумма.

Указывается НеобходимаяСумма и КолвоПозиций.

Нужно найти такие варианты позиций из таблицы, чтобы сумма этих позиций была равна НужнойСумме, а колво позиций, соответственной, КОлвоПозиций.

Перебор, который я спрашивал ранее, по сути перебор индексов, которые нужно просуммировать. По вычисленному варианту я суммирую позиции и сравниваю с НеобходимойСуммой.

Но, есть таблицы, где и по ~40 позиций есть, а с такими уже загибается. Может я не верный подход выбрал?

Пример:
Таблица:
карандаш    10
ручка        20
ластик        30
чернила        40
степлер        20

НеобходимаяСумма 60, КолвоПозиций 3.

Ответ:
Карандаш, Ластик, Степлер
Карандаш, Ручка, Ластик

Если, например, КолвоПозиций будет 2, то ответ:
Ручка, Чернила
Чернила, Степлер
   NS
 
32 - 17.01.13 - 10:53
(31) Задача называется - Задача о рюкзаке.
Метод решения ты естественно выбрал неверный.
   Nikoss
 
33 - 17.01.13 - 11:17
(32), вот блин...
сейчас буду гуглить
 
 
   NS
 
34 - 17.01.13 - 12:15
Самый простой метод решения - направильный перебор с отсечениями.
   NS
 
35 - 17.01.13 - 12:18
Можно решить симлекс-методом.
   Simod
 
36 - 17.01.13 - 12:28


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует