переборные алгоритмы #1879

Не могу найти нужную информацию перебора N-элементного множества по M-чисел (без повторений). Подскажите примерный алгоритм, пожалуйста.

Не совсем понял что надо - наверное еще не проснулся :) Попробуй тут поискать /

Д. Кнут Искусство программировани ЭВМ Целочисленные алгоритмы. RFTM однако...

Дональд Э. Кнут, "Искусство программирования" третье издание, том 1 "Основные алгоритмы",изд. Вильямс, 2000г, ISBN 5-8459-0080-8. Глава 1, раздел 1.2.5 "Перестановки и факториалы".

Спасибо, что поправил, писал спросонья, собрал вместе две книжки...

Спасибо всем, уже ищу Д. Кнута. Может кто процитирует книжку, если не трудно.

Эта книга не содержит рецептов решения частных задач, она даёт крепкое математическое основание для программиста. Поэтому, цитировать её смысла мало, нужно прочитать и понять предыдущие разделы и некоторые последующие. Их немного, всего страниц 75 до и 30 после. За рецептами можно обратиться к англоязычной on-line книге "Numeric Recipies on C", кажется, так. Она мне попадалась лет 5 тому назад, сейчас, увы, на работе осталась. Попробуйте поискать в Нете.

Нашёл всё-таки у себя, "Numeric Recipes in C" называется. Но там более другие вещи, Вашей темы нет. Поэтому, попробуйте что-нибудь другое поискать.

На algolist.manual.ru не нашла моего случая. Есть еще советы? А то нетерпится, или буду ждать понедельника - библиотеки, магазины и т. д. Господа профессионалы - а для вас это трудная задача?

Извините, Nataly, но не приходилось с этим сталкиваться. Поэтому, кроме общих мест, и сказать нечего.

(+) Пункт 1.2

(10 и 11) Спасибо, Дмитрий, примеры хорошие, но мне надо без повторений (например как в лото 5 из 36).

Пардон, полусонный был. Есть предложение сделать M циклов 1..N, 2..N, .... ,M..N Индексы сортировать и записывать в строку i1_i2_..._im Полученные строки заносить в одномерный массив в случае, если их в этом массиве нет.

Ребята, я до сих пор не могу сообразить. Кое-что делаю, но чувствую, что ход мыслей не тот. Поняла, что надо при сочетании по 5 сначала менять 5-й элемент, затем 4-й сдвинуть по индексу на 1 и далее менять 5-й, пока k< N (конечного элемента) и так далее. Натолкните на мысль пожалуйста.

Итерация в данном случае не сильно поможет :) M циклов - это просто прикол :)) Хочу глянуть на код с M > 1000 :) Рекурсия - вот ваш выход, уважаемая Наталья. Приблизительно так: Функция ЕстьЗнач(исхзнач,инд)    Возврат Найти(исхзнач,Строка(инд)); КонецФункции Функция НайтиЗначение(исхзнач)    Для инд=0 по 9 Цикл        Если ЕстьЗнач(исхзнач,инд)<>0 Тогда            Продолжить;        Иначе            Если СтрДлина(исхзнач)=2 Тогда                Сообщить(исхзнач+Строка(инд));                Продолжить;            Иначе                НайтиЗначение(исхзнач+Строка(инд));            КонецЕсли;        КонецЕсли;    КонецЦикла; КонецФункции Процедура Выполнить    НайтиЗначение(""); КонецПроцедуры       Вариант упрощённвый, но представление о задаче должен дать.

Да, маленькие комментарии про непонятные цифры :) От 0 до 9 - этакое представление множества значений N. 2 - Это (M-1), длина выборки. Можно было и в явном виде M, ну да ладно :) Осудите, ежели чего не так. PS: А Кнута я не читал...

:) А я-то думал это по 1С вопрос, колбашу на встроенном языке :) Ежели непонятно, могу переписать на выбранном Вами языке... Короче всего на Лиспе получится :)

Уважаемый Inside, я, конечно поразбираюсь в вашем тексте, но мне нужно на VB6 или псевдокод, если не трудно.

Вот Вам, Наталья, на VB, только если надо выводить результат в определённое место, избавтесь от MsgBox, а то долго нажимать Акей придётся. Тут Len(str + CStr(i)) = 3 - длина выборки в явном виде. Function isexists(str, char)  isexists = InStr(str, char) End Function Sub FindExp(str)  For i = 0 To 9    If isexists(str, CStr(i)) <> 0 Then      GoTo 1    Else      If Len(str + CStr(i)) = 3 Then        MsgBox str + CStr(i)        GoTo 1      Else        FindExp (str + CStr(i))      End If    End If 1:  Next i End Sub Sub Run  FindExp ("") End Sub Успехов!

Да, не ругайте за ГоуТу пажалста, не знаю как "Продолжить" или "Continue" в VB :)

Представьте задачу таким образом: M элементов - это цифры числа, М штук. Например, если М=5, то число из 5 цифр состоит. Теперь надо пперебирать для каждой цифры 1-N значений. Проверяем при этом, чтобы в цифрах не было одинаковых. Начинаем с числа 12345...M. При такой постановке сразу понятно, что M<N, иначе повторения неизбежны.

Вы хотите сказать, что трудоемкость алгоритма при рекурсии меньше, чем при М циклах?

Дмитрий! Тродоёмкость алгоритма несравнимо меньше. Для обсуждения я предлагаю Вам привести свой вариант кода при М > 1000. В предложенном мною варианте изменится пара строк в числовых значениях. Не понял смысла поста, честно :)