Перебор возможных вариантов выборки из массива

@alhaos · Регистрация: 20.02.2019

Студворк — интернет-сервис помощи студентам

Подскажите пожалуйста, алгоритм генерации всех возможных выборов [n] элементов из массива в [m] элементов.

@Shamil1 · 15.04.2021, 15:52

Делаете массив размера m для выбранных индексов.

Для получения следующего выбора:
Для всех разрядов:
Пытаемся увеличить на 1 текущий индекс. (Каждый индекс не должен превышать следующий).
Если удалось, то увеличиваем и возвращаем Истина
Если не удалось, то сбрасываем в начальное значение indexes[i] = i и переходим к следующему.
Если нельзя перейти к следующему, то возвращаем Ложь.

Например, так:

C#
1
2
3
4
5
6
7
8
9
10
11
12
bool Next(int[] indexes, int maxIndex)
{
    int i = 0;
    while(i < indexes.Length - 1)
    {
        if(++indexes[i] < indexes[i + 1])
            return true;
        indexes[i] = i++;
    }
 
    return ++indexes[i] < maxIndex;
}

Функцию можно использовать в цикле

C#
1
do {} while(Next(indexes, m));

@Mikhaylo · 15.04.2021, 20:23

Комбинаторика задает уточняющие вопросы:
1. Элементы в m-массиве повторяются?
2. Порядок элементов в выборе важен?

В зависимости от ответа на эти вопросы, даются формулы вычисления числа сочетаний, перестановок, размещений с повторением или без. Всего 6 формул и соответственно алгоритмов перебора.

Еще есть вопрос комбинаторики: "А есть ли выбор?", этот вопрос эквивалентен вопросу "m != n?". На этот вопрос в условии задачи есть ответ, на первые два - нет.
Алгоритмы искать у Д. Кнута.

@alhaos · 15.04.2021, 20:55 **[ТС]**

В массиве элемента не повторяются, порядок выбранных элементов важен.

Добавлено через 2 минуты
n < m

Добавлено через 32 секунды
Shamil1, спасибо, буду вникать

@Mikhaylo · 15.04.2021, 21:14

Тогда ваш случай - размещения без повторений, число элементов A(n, m) = n! / (n - m)! Алгоритмы размещений без повторений в интернете можно найти.

@alhaos · 16.04.2021, 06:19 **[ТС]**

Mikhaylo, Благодарю за пояснения.

Новые блоги и статьи Все статьи Все блоги /
Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .
Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .

@alhaos 1929 / 545 / 154 Регистрация: 20.02.2019 Сообщений: 2,665 Записей в блоге: 66

	Перебор возможных вариантов выборки из массива 15.04.2021, 15:01. Показов 1107. Ответов 5 Метки нет (Все метки) Подскажите пожалуйста, алгоритм генерации всех возможных выборов [n] элементов из массива в [m] элементов. 0

@Mikhaylo 691 / 575 / 75 Регистрация: 20.09.2014 Сообщений: 3,751
	15.04.2021, 20:23
	Комбинаторика задает уточняющие вопросы: 1. Элементы в m-массиве повторяются? 2. Порядок элементов в выборе важен? В зависимости от ответа на эти вопросы, даются формулы вычисления числа сочетаний, перестановок, размещений с повторением или без. Всего 6 формул и соответственно алгоритмов перебора. Еще есть вопрос комбинаторики: "А есть ли выбор?", этот вопрос эквивалентен вопросу "m != n?". На этот вопрос в условии задачи есть ответ, на первые два - нет. Алгоритмы искать у Д. Кнута. 0

@alhaos 1929 / 545 / 154 Регистрация: 20.02.2019 Сообщений: 2,665 Записей в блоге: 66
	15.04.2021, 20:55 [ТС]
	В массиве элемента не повторяются, порядок выбранных элементов важен. Добавлено через 2 минуты n < m Добавлено через 32 секунды Shamil1, спасибо, буду вникать 0

@Mikhaylo 691 / 575 / 75 Регистрация: 20.09.2014 Сообщений: 3,751
	15.04.2021, 21:14
	Тогда ваш случай - размещения без повторений, число элементов A(n, m) = n! / (n - m)! Алгоритмы размещений без повторений в интернете можно найти. 1

@alhaos 1929 / 545 / 154 Регистрация: 20.02.2019 Сообщений: 2,665 Записей в блоге: 66
	16.04.2021, 06:19 [ТС]
	Mikhaylo, Благодарю за пояснения. 0

Опции темы