Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.69/48: Рейтинг темы: голосов - 48, средняя оценка - 4.69
1123 / 794 / 101
Регистрация: 01.02.2011
Сообщений: 1,880
Записей в блоге: 1
1

Комбинаторика. Нужна реализация алгоритма размещений без повторений

25.04.2015, 15:13. Показов 9564. Ответов 6
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте. Собственно сабж. В инете ничего нормального не нашёл. Есть конечно реализация алгоритма размещения с повторениями, но мне нужно без повторений.
Про сами размещения можно прочитать тут и тут.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.04.2015, 15:13
Ответы с готовыми решениями:

Сочетания без повторений, Комбинаторика, Дискретная математика
Помогите, пожалуйста, решить данную задачу на C++ или С. Задано натуральное число n<=20 и...

Комбинаторика.Подсчитать число размещений с повторениями
#pragma hdstop #pragma argsused #include <math.h> #include <tchar.h> #include <iostream.h>...

Солько существует размещений без повторений по четыре элемента множества?
Дано множество М ={1,2,.,100}сколько существует размещений без повторение с элементов множества М...

Сочетание без повторений (комбинаторика)
Всем доброго времени суток. К примеру есть 6 чисел и необходимо составить двухэлементные...

6
Эксперт PHP
3106 / 2591 / 1219
Регистрация: 14.05.2014
Сообщений: 7,236
Записей в блоге: 1
25.04.2015, 15:18 2
Цитата Сообщение от kzru_hunter Посмотреть сообщение
но мне нужно без повторений.
Вы о сочетаниях говорите?
0
1123 / 794 / 101
Регистрация: 01.02.2011
Сообщений: 1,880
Записей в блоге: 1
25.04.2015, 15:23  [ТС] 3
Цитата Сообщение от Kerry_Jr Посмотреть сообщение
Вы о сочетаниях говорите?
http://www.matburo.ru/tv_komb.php
0
Эксперт PHP
3106 / 2591 / 1219
Регистрация: 14.05.2014
Сообщений: 7,236
Записей в блоге: 1
25.04.2015, 15:24 4
kzru_hunter, да ходил я по этим ссылкам, только мне это не нужно. Что Вы считаете повторениями?
0
1123 / 794 / 101
Регистрация: 01.02.2011
Сообщений: 1,880
Записей в блоге: 1
25.04.2015, 15:28  [ТС] 5
Цитата Сообщение от Kerry_Jr Посмотреть сообщение
Что Вы считаете повторениями?
Создай отдельно тему. Тебе там ответят, что это такое. Или сходи по ссылкам и спокойно прочитай, там все написано.
Вопросы в теме задаю я.
0
244 / 164 / 133
Регистрация: 30.09.2012
Сообщений: 690
25.04.2015, 15:57 6
Так первая же формула в ссылке на википедию и есть формула размещений без повторений (оно же количество размещений) или что-то другое надо?
0
1123 / 794 / 101
Регистрация: 01.02.2011
Сообщений: 1,880
Записей в блоге: 1
26.04.2015, 11:01  [ТС] 7
Цитата Сообщение от Gr1f0nn Посмотреть сообщение
Так первая же формула в ссылке на википедию и есть формула размещений без повторений
там формула вычисления количества размещений, а мне нужны сами размещения.

Добавлено через 17 часов 36 минут
Аллилуйя! Нашёл все-таки! Оказывается, на английском рассматриваемые размещения называются "K-permutations". Используя поиск, нашёл статью. Там был код, переделал под стиль C.

Проверил - всё супер! Плюсы:
1) Функция нерекурсивная.
2) Мало кода (разобраться не составит труда).
3) Стиль C
4) Генерирует по возрастанию
5) Очень быстро генерирует (но всё равно чуть медленнее алгоритма Нарайаны, который генерирует перестановки).

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// генерирует следующее размещение, используя массив a
// n - всего элементов
// k - вместимость размещения
int GenerateNextPermKN(int *a, int k, int n)
{
        int edge, j, i, tmp;
        edge = k - 1;
 
        // find j in (k…n-1) where a[j] > a[edge]
        j = k;
        while ( (j < n) && (a[edge] >= a[j]) ) ++j;
 
        if (j < n)
        {
                // swap a[egde], a[j]
                tmp = a[edge], a[edge] = a[j], a[j] = tmp;
        }
        else
        {
                // reverse a[k] to a[n-1]
                for (i = k, j=n-1;  i<j;  i++, j--)
                {
                        tmp = a[i], a[i] = a[j], a[j] = tmp;
                }
 
                // find rightmost ascent to left of edge
                i = edge - 1;
                while (i >= 0 && a[i] >= a[i+1]) --i;
 
                if (i < 0) return 0;           // no more permutations
 
                // find j in (n-1…i+1) where aj > ai
                j = n - 1;
                while (j > i && a[i] >= a[j]) --j;
 
                // swap a[i], a[j]
                tmp = a[i], a[i] = a[j], a[j] = tmp;
 
                // reverse a[i+1] to an-1
                for (i = i+1, j=n-1;  i<j;  i++, j--)
                {
                        tmp = a[i], a[i] = a[j], a[j] = tmp;
                }
        }
        return 1;
}
0
26.04.2015, 11:01
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.04.2015, 11:01
Помогаю со студенческими работами здесь

Нужна реализация алгоритма SHA-224
Есть ли у кого-нибудь готовая реализация данного алгоритма? В сети нашел только HashLib, но там...

Выборка размещений с заданным количеством повторений
Написал выборку всех размещений с повторениями. Существуют ли какие-нибудь алгоритмы для...

Нужна реализация итерационного алгоритма наибольшей общей подпоследовательности
Или я нуб в гугле, или реализации этого алгоритма на паскале в сети нет. Мне нужен именно...

Количество размещений без повторениий в возрастающем порядке
Подсчитать количество размещений без повторениий в возрастающем порядке. Например:...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru