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

Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1 - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.65
Iworb
анимешник++
 Аватар для Iworb
93 / 60 / 2
Регистрация: 03.11.2009
Сообщений: 411
30.03.2011, 22:04     Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1 #1
В функцию передаем n и k, она возвращает матрицу размерами C(n,k) строк на k столбцов
К примеру n = 4, k = 2 (числа 0 1 2 3)
Функция должна вернуть:
Код
01
02
03
12
13
23
Помогите пожалуйста, кто знает комбинаторику.

Добавлено через 24 минуты
(C(n,k) я считаю программно, поэтому описывать не надо)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.03.2011, 22:04     Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1
Посмотрите здесь:

вычислить все сочетания из N элементов по M C++
C++ необходимо каким-то образом пронумеровать все сочетания, никак не могу придумать алгоритм
Преобразовать строку , заменив все сочетания “авс” на ”ghn” C++
C++ Сгенерировать 10 чисел в интервале от 1 до 50 и посчитать, сколько среди них чисел > 15
C++ Из заданной строки получить новую, заменив в ней все сочетания «abcd» на «abc».
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
30.03.2011, 22:18     Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1 #2
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
#include <iostream>
#include <string>
#include <math.h>
 
using namespace std;
using std::string;
 
int main()
{
  int n, k, i, p, c, q, l;
  string s;
 
  cin >> k >> n;
 
  l = pow(n, k);
 
  for (i = 0; i < l; i++){
    p = i; s = ""; c = 0;
 
    while (pow(n, c) <= p) c++;
 
    for (q = 0; q < c; q++) {
      s += (char) (p % n + 48);
      p /= n;
    }
 
    if (s.length() < k) for (p = 0; p < k - s.length(); p++) cout << "0";
 
    for (p = 0; p < s.length(); p++) cout << s[s.length() - p - 1];
 
    cout << endl;
  }
 
  return 0;
}
вроде, так, а пример ваш, вроде, неточен, если я ничего не путаю
Iworb
анимешник++
 Аватар для Iworb
93 / 60 / 2
Регистрация: 03.11.2009
Сообщений: 411
30.03.2011, 22:39  [ТС]     Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1 #3
нет, вы немного не поняли. Вы делаете все перестановки, мне же нужны все сочетания (т.е. одно и тоже число нельзя использовать 2 раза - нету 00 и 11). Если в Вашей программе это убрать, тогда вроде то что нужно.
Кому интересно - есть готовый код на перле - http://codepad.org/zFGF5Cy1#output
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
30.03.2011, 22:48     Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1 #4
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
#include <iostream>
#include <string>
#include <math.h>
 
using namespace std;
using std::string;
 
int main()
{
  int n, k, i, p, c, q, l; bool get_out;
  string s, t;
 
  cin >> k >> n;
 
  l = pow(n, k);
 
  for (i = 0; i < l; i++){
    p = i; s = ""; c = 0;
 
    while (pow(n, c) <= p) c++;
 
    for (q = 0; q < c; q++) {
      s += (char) (p % n + 48);
      p /= n;
    }
 
    if (s.length() < k) for (p = 0; p < k - s.length(); p++) cout << "0";
 
    get_out = false;
    for (q = 0; q < c; q++) {
      t = "";
      for (p = 0; p < s.length(); p++) t += (char) (p + 48);
      if (t == s) get_out = true;
    }
 
    if (get_out) continue;
 
    for (p = 0; p < s.length(); p++) cout << s[s.length() - p - 1];
 
    cout << endl;
    
  }
 
  return 0;
}
Iworb
анимешник++
 Аватар для Iworb
93 / 60 / 2
Регистрация: 03.11.2009
Сообщений: 411
30.03.2011, 23:17  [ТС]     Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1 #5
Вот что программа выдала в результате:
Код
3
6
000
001
002
003
004
005
0011
012
013
014
015
020
021
022
023
024
025
030
031
Для продолжения нажмите любую клавишу . . .
До истины далековато... да и одно число из 4х цифр

Добавлено через 25 минут
Попробовал сделать из того кода:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void perl(int n, int k)
{
    std::vector<int> a(k);
    for(int i=0;i<a.size();i++) a[i]=i;
    print(a);
    for(;;)
    {
        int j;
        for(j=0;j<k-1;j++)
            if ( a[j] + 1 < a[j + 1] )
                break;
        if(!(j<k-1))
        {
            if(a[k-1]<n-1)
                j=k-1;
            else
                break;
        }
        a[j]++;
        print(a);
        for(int i=0;i<j-1;i++) a[i]=i;
    }
}
Но выводит не все комбинации...
Mr.X
Эксперт С++
 Аватар для Mr.X
2802 / 1578 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
31.03.2011, 11:45     Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1 #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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/////////////////////////////////////////////////////////////////////////////////////////
//В функцию передаем n и k, она возвращает матрицу размерами C(n,k) строк на k столбцов
//К примеру n = 4, k = 2 (числа 0 1 2 3)
//Функция должна вернуть:
//
//01
//02
//03
//12
//13
//23
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector<int>            T_combination;
typedef std::vector<T_combination>  T_combinations;
/////////////////////////////////////////////////////////////////////////////////////////
void  fill_combinations(int  n, int  k, T_combinations&  combinations)
{
    T_combination  combination_cur(k, -1);    
    for(int  ind = 0;;)    
    {         
        while(combination_cur[ind] == n - k + ind)
        {            
            if(--ind < 0) return;
        }        
        
        int  diff = combination_cur[ind] + 1 - ind;
        
        for(;; ++ind)
        {            
            combination_cur[ind] = ind + diff;            
            if(ind == k - 1) break;            
        }
        combinations.push_back(combination_cur);        
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Для вычисления сочетаний C(n, k) введите:"
              << std::endl
              << '\t'
              << "n = ";
 
    int  n = 0;
    std::cin >> n;
 
    std::cout << '\t'
              << "k = ";
 
    int k = 0;
    std::cin >> k;
 
    T_combinations  combinations;
    fill_combinations(n, k, combinations);
    std::cout << std::endl
              << "Все "
              << combinations.size()
              <<" комбинаций C("
              << n
              << ", "
              << k
              << "):"
              << std::endl;
 
    for(T_combinations::const_iterator  comb_it = combinations.begin();
        comb_it != combinations.end(); ++comb_it)
    {
        std::copy(comb_it->begin(), comb_it->end(), 
                  std::ostream_iterator<int>(std::cout, " "));
        std::cout << std::endl;
    }
    std::cout << std::endl;
}
Iworb
анимешник++
 Аватар для Iworb
93 / 60 / 2
Регистрация: 03.11.2009
Сообщений: 411
31.03.2011, 19:11  [ТС]     Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1 #7
Mr.X, Спасибо, скажите, а вот это
Код
error C2039: 'ostream_iterator' : is not a member of 'std'
можно сделать по другому как-нибудь? Странно конечно, но ругается, что нет такого - 10я студия.

Добавлено через 17 минут
UPD переделал - простенькую распечатку сделал - теперь всё нормально, спасибо!
Mr.X
Эксперт С++
 Аватар для Mr.X
2802 / 1578 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
31.03.2011, 20:53     Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1 #8
Цитата Сообщение от Iworb Посмотреть сообщение
Mr.X, Спасибо, скажите, а вот это
Код
1
error C2039: 'ostream_iterator' : is not a member of 'std'
можно сделать по другому как-нибудь? Странно конечно, но ругается, что нет такого - 10я студия.
Ну, вообще-то надо
C++
1
#include <iterator>
включить. У меня в 2008-й студии и так компилирует, поэтому я не заморачивался.
Байт
 Аватар для Байт
13974 / 8805 / 1227
Регистрация: 24.12.2010
Сообщений: 15,949
29.09.2015, 15:53     Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1 #9
Цитата Сообщение от Iworb Посмотреть сообщение
можно сделать по другому как-нибудь?
Комбинаторика на С++
Посмотрите. Может быть подойдет.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.09.2015, 16:51     Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1
Еще ссылки по теме:

C++ Сгенерировать все k -элементные подмножества из N
C++ Из заданной строки получить новую, заменив в ней все сочетания «abcd» на «abc»
STL: найти все максимальные цепочки подряд идущих положительных чисел с указанием длины каждой цепочки C++

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

Или воспользуйтесь поиском по форуму:
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
29.09.2015, 16:51     Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1 #10
еще вариант.

C++ (Qt)
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
#include <iostream>
 
using namespace std;
 
bool used[123];
int n, k;
 
void rec(int lst, int cnt) {
    if(cnt == k) {
        for(int i = 0; i < n; i++) {
            if(used[i]) {
                cout << i << ' ';
            }
        }
        cout << endl;
        return;
    }
 
    if(lst + 1 >= n) {
        return;
    }
 
    used[lst + 1] = true;
    rec(lst + 1, cnt + 1);
    used[lst + 1] = false;
    rec(lst + 1, cnt);
    return;
}
 
int main() {
    cin >> n >> k;
    rec(-1, 0);
    return 0;
}
Yandex
Объявления
29.09.2015, 16:51     Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1
Ответ Создать тему

Метки
комбинаторика, сочетания
Опции темы

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