Форум программистов, компьютерный форум CyberForum.ru

Комбинаторика - C++

Восстановить пароль Регистрация
 
NillK
 Аватар для NillK
0 / 0 / 0
Регистрация: 26.09.2013
Сообщений: 11
27.12.2013, 12:47     Комбинаторика #1
Помогите написать алгоритм для вычисления количество непустых последовательностей из ряда чисел. Или кинте ссылочку, где почитать.
Что я имею ввиду?
Пример :
Входные данные : 1 3 3 4
решение:
1 3 3 4
1 3 4
1 3
1 4
1
3 3 4
3 4
3 3
3
4
Вывод: 10.

Спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.12.2013, 12:47     Комбинаторика
Посмотрите здесь:

комбинаторика C++
Комбинаторика C++
C++ Комбинаторика на С++
комбинаторика в программировании C++
C++ Комбинаторика и переборные алгоритмы
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
27.12.2013, 14:18     Комбинаторика #2
Цитата Сообщение от NillK Посмотреть сообщение
последовательностей из ряда чисел
подпоследовательностей м.б ?

Добавлено через 1 минуту
почему то мне кажется это будет 1+2+3+4 (зависит от длины начального ряда)

Добавлено через 14 минут
а нет мое предположение бред
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.12.2013, 16:09     Комбинаторика #3
Что-то логики не видно:
Цитата Сообщение от NillK Посмотреть сообщение
Входные данные : 1 3 3 4
решение:
1 3 3 4
1 3 4
1 3
1 4
1
а почему нет: 1 3 3 ?
NillK
 Аватар для NillK
0 / 0 / 0
Регистрация: 26.09.2013
Сообщений: 11
27.12.2013, 17:00  [ТС]     Комбинаторика #4
Пропустил, значит там ответ 11
XRoy
848 / 698 / 217
Регистрация: 15.04.2013
Сообщений: 2,047
Записей в блоге: 5
27.12.2013, 17:33     Комбинаторика #5
NillK, Разве здесь не будет 16 вариантов. Тогда получается формула размещение 2n
DiffEreD
 Аватар для DiffEreD
1420 / 757 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
27.12.2013, 17:57     Комбинаторика #6
Ну не знаю, может что типа такого:
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
#include <iostream>
#include <algorithm>
#include <set>
 
int main()
{
   std::string s = "1334";
   //std::sort(s.begin(), s.end());
 
   size_t number;
   std::set<size_t> numbers;
   do {
      number = std::stoi(s);
      numbers.insert(number);
      while (number /= 10)
         numbers.insert(number);
   } while (std::next_permutation(s.begin(), s.end()));
 
   std::cout << "Count: " << numbers.size() << "\n";
   for (size_t i : numbers) std::cout << i << "\n";
 
   std::cout << "\n\nDone." << std::endl;
   return 0;
}
Добавлено через 3 минуты
Кликните здесь для просмотра всего текста
Count: 34
1
3
4
13
14
31
33
34
41
43
133
134
143
313
314
331
334
341
343
413
431
433
1334
1343
1433
3134
3143
3314
3341
3413
3431
4133
4313
4331
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
27.12.2013, 18:22     Комбинаторика #7
NillK, расскажите подробнее об исходной последовательности. есть ли какие-то ограничения, например, может ли быть исходная последовательность такой: 3134 или она должна быть неубывающей (есть одна идея, но она будет работать только для неубывающих последовательностей).

Добавлено через 1 минуту
DiffEreD, нет, порядок чисел в последовательности важен, его нельзя менять
XRoy
848 / 698 / 217
Регистрация: 15.04.2013
Сообщений: 2,047
Записей в блоге: 5
27.12.2013, 19:18     Комбинаторика #8
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
#include <iostream>
#include <cstring>
 
using namespace std;
 
void createMask(int n, bool *mask, const int &size);
 
int main(int argc, char const *argv[])
{
    int arr[] = {1, 2, 3, 4};
    int i, j; int n = (sizeof(arr) / sizeof(arr[0]));
    int stop = 1 << n;
    bool mask[n];
 
    for ( i = 0; i < stop; ++i )
    {
        createMask(i, mask, n);
        for ( j = 0; j < n; ++j )
        {
            if (mask[j]) cout << arr[j] << " ";
        }
        cout << endl;
    }
 
    return 0;
}
 
void createMask(int n, bool *mask, const int &size)
{
    int const radix = 2;
    int i = 0;
    memset(mask, 0, size);
    while ( n >= radix )
    {
        mask[i++] = n % radix;
        n /= 2;
    }
    mask[i] = n % radix;
}
Кликните здесь для просмотра всего текста


1
2
1 2
3
1 3
2 3
1 2 3
4
1 4
2 4
1 2 4
3 4
1 3 4
2 3 4
1 2 3 4
NillK
 Аватар для NillK
0 / 0 / 0
Регистрация: 26.09.2013
Сообщений: 11
27.12.2013, 23:11  [ТС]     Комбинаторика #9
Цитата Сообщение от XRoy Посмотреть сообщение
NillK, Разве здесь не будет 16 вариантов. Тогда получается формула размещение 2n
Важна последовательность, важна неповторяемость

Добавлено через 7 минут
Последовательность состоит из натуральных x, x принадлежит от 1 до 1 000 000, числа написаны через пробел, заранее известна длинна последовательности (вводится)

Добавлено через 8 минут
XRoy, при вводе повторяющихся чисел появляются ошибки.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4919 / 2662 / 243
Регистрация: 29.11.2010
Сообщений: 7,399
27.12.2013, 23:45     Комбинаторика #10
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
#include <iostream>
#include <clocale>
 
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "");
    const int N = 6;
    int A[N];         // имеем множество A {1, ... N}
    for (int i = 0; i < N; i++)
        A[i] = i + 1; // заполняем множество
    int a[N] = {0};   // надо ли включать элемент множества
    int counter = 0;  // счетчик
    while (a[0] != 2) // пока не прошли все элементы
    {
        for (int i = 0; i < N; i++) // выводим подмножество
            if(a[i]) // если нужно печатать
                cout << A[i] << ' ';
        cout << endl;
 
        a[N-1]++; // увеличиваем последний разряд
        for (int i = N - 1; i > 0; i--) // если нужен сдвиг
            if(a[i] == 2) // увеличиваем след. разряд
            {
                a[i-1]++;
                a[i] = 0;
            }
        counter++; // увеличиваем счетчик на один
    }
    cout << "Всего подмножеств: " << counter << endl;
}
NillK
 Аватар для NillK
0 / 0 / 0
Регистрация: 26.09.2013
Сообщений: 11
28.12.2013, 01:50  [ТС]     Комбинаторика #11
MrGluck, а как при этом он будет обрабатывать последывательность например такую: 2 1 2 3
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4919 / 2662 / 243
Регистрация: 29.11.2010
Сообщений: 7,399
28.12.2013, 01:58     Комбинаторика #12
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
#include <iostream>
#include <clocale>
 
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "");
    const int N = 4;
    int A[N] = {2, 1, 2, 3};
    int a[N] = {0};   // надо ли включать элемент множества
    int counter = 0;  // счетчик
    while (a[0] != 2) // пока не прошли все элементы
    {
        for (int i = 0; i < N; i++) // выводим подмножество
            if(a[i]) // если нужно печатать
                cout << A[i] << ' ';
        cout << endl;
 
        a[N-1]++; // увеличиваем последний разряд
        for (int i = N - 1; i > 0; i--) // если нужен сдвиг
            if(a[i] == 2) // увеличиваем след. разряд
            {
                a[i-1]++;
                a[i] = 0;
            }
        counter++; // увеличиваем счетчик на один
    }
    cout << "Всего подмножеств: " << counter << endl;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.12.2013, 02:21     Комбинаторика
Еще ссылки по теме:

Комбинаторика C++
C++ Комбинаторика. Сочетания
Покерная комбинаторика C++

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

Или воспользуйтесь поиском по форуму:
tcennoc
1 / 1 / 0
Регистрация: 22.11.2013
Сообщений: 35
28.12.2013, 02:21     Комбинаторика #13
Это может пригодиться?
Yandex
Объявления
28.12.2013, 02:21     Комбинаторика
Ответ Создать тему
Опции темы

Текущее время: 11:32. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru