Найти все сочетания с повторениями из букв A, B, C, D заданного размера

@Valeriiia · Регистрация: 01.07.2017

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

Как написать следующую функцию на с++?

def possible_variants(k):
return [''.join(x) for x in product('ABCD', repeat=k)]

То есть найти все сочетания с повторениями из букв A, B, C, D размером k.

Например, при k=2:
AA
AB
AC
AD
BB

и т.д.

@GbaLog- · 29.01.2018, 15:35

del

@Valeriiia · 29.01.2018, 15:40 **[ТС]**

itertools.product(*iterables[, repeat])
Cartesian product of input iterables.

Roughly equivalent to nested for-loops in a generator expression. For example, product(A, B) returns the same as ((x,y) for x in A for y in B).

The nested loops cycle like an odometer with the rightmost element advancing on every iteration. This pattern creates a lexicographic ordering so that if the input’s iterables are sorted, the product tuples are emitted in sorted order.

@Avaddon74 · 29.01.2018, 16:16

Я только такое смог придумать

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
#include <iostream>
#include <string>
 
using namespace std;
 
void func(int k) {
    string str = "ABCD";
    if (k > 0) for (const auto &ch1 : str) {
        if (k > 1) for (const auto &ch2 : str) {
            if (k > 2) for (const auto &ch3 : str) {
                if (k > 3) for (const auto &ch4 : str) {
                    cout << ch1 << ch2 << ch3 << ch4 << endl;
                } else cout << ch1 << ch2 << ch3 << endl;
            } else cout << ch1 << ch2 << endl;
        } else cout << ch1 << endl;
    } 
    cout << endl;
}
 
int main() {
    int k;
    cout << "Enter number: ";
    cin >> k;
 
    func(k);
 
    return 0;
}

@Valeriiia · 29.01.2018, 16:20 **[ТС]**

но эта программа не сработает, если k больше 4 )) (c повторениями же)

@Avaddon74 · 29.01.2018, 16:31

Сообщение от Valeriiia

но эта программа не сработает, если k больше 4

Сработает как k==4
но не сработает если строку изменить на ABCDE и т.д.

@Valeriiia · 29.01.2018, 16:33 **[ТС]**

это да) но нужно размера k, вот в чем загвоздка(

@Avaddon74 · 29.01.2018, 16:37

Когда k больше 4-х то все сработает как k==4

@regio1961 · 29.01.2018, 17:46

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
 #include <iostream>
 //--------------------------------------------------------
 bool next_comb( int index[], const int &n, const int &m )
 {
   int j = m - 1;
       while ( index[ j ] == n && j >= 0 )
          j--;
       if ( j < 0 )
          return false;
       if ( index[ j ] >= n )
          j--;
   index[ j ]++;
      if ( j == m - 1 )
         return true;
      for ( int k = j + 1; k < m; k++ )
         index[ k ] = index[ j ];
   return true;
 }
 //--------------------------------------------------------
 int main()
 {
   char char_set[] = { 'A', 'B', 'C', 'D' };
   int N = sizeof( char_set ) / sizeof( char_set[ 0 ] );
       for( int i = 0; i < N; ++i )
          std::cout << char_set[ i ] << " ";
   std::cout << std::endl;
   int n = 2;
   int k = N > n ? N : n;
   int *index = new int [ k ];
       for ( int i = 0; i < k; i++ )
           index[i] = 1;
       do
       {
             for( int i = 0; i < n; ++i )
                std::cout << char_set[ index[ i ] - 1 ] << " ";
         std::cout << std::endl;
       }
       while ( next_comb( index, N, n ) );
   delete [] index;
   //std::cin.get();
 }

Байт · 29.01.2018, 18:30

По-простому надо просто перебрать все числа в 4-ичной системе счисления определенной (k) длины...
Для проверки - число комбинаций = 4^k.
Если буков не 4, а скажем, 5, надо в предыдущем тексте "4" заменить на "5" и так далее и тому подобное...

Добавлено через 9 минут
Что-нибудь в таком духе

C++
1
2
3
4
5
6
7
8
9
int M = (1 << 2*k); // для 4 умножения можно заменить сдвигом
for(int i = 0; i<M; i++) {
  int n = i;
  for(int j; j<k; j++) {
    cout << 'A' + n%4;
    n /= 4;
  }
  cout << endl;
}

@outoftime · 29.01.2018, 21:51

Valeriiia, если переводить из питона тогда и итераторы реализовать. 100 лет на плюсах не писал, на быструю руку вот что вышло:

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
#include <iostream>
#include <iterator>
#include <vector>
 
 
class product 
{
    typedef product* product_ptr;
    typedef std::vector<std::string> vstring;
 
    const vstring data;
    size_t length;
    const size_t repeat;
public:
    class iterator : public std::iterator<
        std::input_iterator_tag,
        std::string,
        long,
        std::string*,
        std::string&> 
    {
        size_t step;
        const product_ptr prod;
    public:
        explicit iterator(const size_t &step, const product_ptr &prod) : step(step), prod(prod) { }
        iterator &operator++() { ++step; return *this; }
        bool operator==(iterator other) const { return step == other.step && prod == other.prod; }
        bool operator!=(iterator other) const { return !(*this == other); }
        std::string operator*() const {
            const size_t len = prod->repeat * prod->data.size();
            char *buffer = new char[len+1]{0};
            size_t i = len - 1, 
                   temp_step = step;
            for (size_t r = 0; r < prod->repeat; ++r) {
                for (vstring::const_reverse_iterator it = prod->data.crbegin(); it != prod->data.crend(); it++) {
                    size_t pos = temp_step % it->size();
                    temp_step /= it->size();
                    buffer[i--] = (*it)[pos];
                }
            }
            return std::string(buffer);
        }
    };
 
    product(const vstring &value, const int repeat=1) : data(value), repeat(repeat) {
        size_t len = 1;
        for (const auto &a : value) len *= a.size();
        length = len;
        for (size_t i = 1; i < repeat; ++i) length *= len;
    }
    iterator begin() const { return iterator(0, product_ptr(this)); }
    iterator end() const { return iterator(length, product_ptr(this)); }
};
 
 
int main() {
    for (const std::string data : product({"ABCD"}, 2)) {
        std::cout << data << std::endl;
    }
}

Что хочу доделать:
- избавиться от product_ptr (std::shared_ptr использовать или std::week_ptr)
- избавиться от product.length параметра который не константный в пользу вектора итераторов и переписать product::iterator.operator* с использованием другого подхода.

Если кто из старожил заглянет, прокоментируйте код, пожалуйста.

Байт · 29.01.2018, 22:15

Valeriiia, перечитывая тему, закрались у меня сомнения. Порядок букв важен? То есть AABB и BBAA, ABBA - это разные комбинации? Если разные, тогда мое решение рулит. Если они все считаются за одну, тогда нужен другой алгоритм.

Добавлено через 13 минут
Тогда задача сводится к нахождению всех целых неотрицательных решений уравнения x1 + x2 + x3 + x4 = k
Где-то на форуме такая задача уже была...

Добавлено через 2 минуты
Число таких комбинаций находится по формуле C_k+m-1^m-1, m=4

@alex white · 29.01.2018, 22:17

C++
1
2
3
4
5
6
7
8
9
10
11
12
void combinations(int k, const std::string& alphabet, string s="")
{
    if(k == 0)
        cout << s << endl;
    else
    {
        for(char c : alphabet)
        {
            combinations(k-1, alphabet, s + c);
        }
    }
}

Для наглядности все операции со строками здесь иммутабельные, но переделать труда не составит

@outoftime · 29.01.2018, 22:27

Байт, вот дока питона, там есть псевдореализация product https://docs.python.org/3/libr... ls.product

А вот описание того, что она делает: https://en.wikipedia.org/wiki/Cartesian_product

@Avaddon74 · 29.01.2018, 23:40

Вот, универсальная. Можно передавать саму строку, а можно и не передавать, это лучшее что смог придумать

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <string>
 
using namespace std;
 
void func(int k, string str = "ABCD", string chars="") {
    if (k > 0 && k <= str.size()) for (const auto &ch : str) {
        if (k == 1) cout << chars << ch << endl;
        func(k - 1, str, chars + ch);
    }
}
 
int main() {
    int k;
    cout << "Enter number: ";
    cin >> k;
 
    func(k);
 
    return 0;
}

Байт · 29.01.2018, 23:57

Сообщение от outoftime

Байт, вот дока питона, там есть

Понимаете, меня не так уж интересует конкретное решение, мне интересно свои косточки поразмять. В этот раз, кажется, не сложилось, я разминался на другой задаче. В свое оправдание могу сказать, что стартовый топик не совсем точно описал ситуацию, а на вопрос в посте 12 ТС пока не ответил. Особых претензий в этом смысле не имею, многозначность трактовок тут встречается сплошь и рядом, и это даже интересно, оттрактовать ее тем или иным образом. В конце концов это приводит к нескольким задачам, каждую из которых может быть решать интересно.
Ваше решение, вполне возможно, что и блистательное, смотреть не стал из соображений, изложенных выше.
Всем - удачи!

Добавлено через 3 минуты
Пятая строка стартового примера конечно могла навести на мысль, что когда есть АВ, ВА уже никого не интересует. Но я не проинтуичил, увы!

@Avaddon74 · 29.01.2018, 23:59

alex white, Только сейчас заметил твой пример

Чувствую себя копипастой

)

@outoftime · 30.01.2018, 00:20

Байт, 101 строка блистательности на итераторах

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <iterator>
#include <vector>
 
class product
{
    typedef product *product_ptr;
    typedef std::vector<std::string> vstring;
    typedef std::vector<std::string::const_iterator> vstring_iter;
 
    const vstring data;
    const size_t repeat;
 
  public:
    class iterator : public std::iterator<
                         std::input_iterator_tag,
                         std::string,
                         long,
                         std::string *,
                         std::string &>
    {
        const product_ptr prod;
        vstring_iter iters;
 
      public:
        iterator(const vstring_iter &iters, const product_ptr &prod) : iters(iters), prod(prod) { }
        iterator &operator++();
        bool operator==(const iterator &) const;
        bool operator!=(const iterator &) const;
        std::string operator*() const;
    };
 
    product(const vstring &value, const int repeat = 1) : data(value), repeat(repeat) {}
    iterator begin() const;
    iterator end() const;
};
 
int main()
{
    for (const std::string data : product({"ABCD", "xy"}))
        std::cout << data << std::endl;
    for (const std::string data : product({"01"}, 3))
        std::cout << data << std::endl;
}
 
//
// product implementation
//
 
product::iterator product::begin() const
{
    vstring_iter iters(data.size() * repeat);
    for (size_t i = 0; i < iters.size(); ++i)
        iters[i] = data[i % data.size()].begin();
    return iterator(iters, product_ptr(this));
}
 
product::iterator product::end() const
{
    vstring_iter iters(data.size() * repeat);
    iters[0] = data[0].end();
    for (size_t i = 1; i < iters.size(); ++i)
        iters[i] = data[i % data.size()].begin();
    return iterator(iters, product_ptr(this));
}
 
//
// product::iterator implementation
//
 
product::iterator &product::iterator::operator++()
{
    const size_t data_size = prod->data.size();
    for (int i = iters.size() - 1; i >= 0; --i)
    {
        ++iters[i];
        if (i && iters[i] == prod->data[i % data_size].end())
            iters[i] = prod->data[i % data_size].begin();
        else
            break;
    }
    return *this;
}
 
std::string product::iterator::operator*() const
{
    const size_t len = prod->repeat * prod->data.size();
    char *buffer = new char[len + 1]{ 0 };
    for (int i = len - 1; i >= 0; --i)
        buffer[i] = *iters[i];
    return std::string(buffer);
}
 
bool product::iterator::operator==(const product::iterator &other) const
{
    if (prod != other.prod || iters.size() != other.iters.size())
        return false;
    return iters == other.iters;
}
 
bool product::iterator::operator!=(const product::iterator &other) const { return !(*this == other); }

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
$ g++ -o run run.cpp -std=gnu++11
$ ./run
Ax
Ay
Bx
By
Cx
Cy
Dx
Dy
000
001
010
011
100
101
110
111

Valeriiia, тебе особенно рекомендую посмотреть (и проверить есть ли утечки памяти) для практики.

@Valeriiia · 30.01.2018, 13:21 **[ТС]**

Байт, порядок важен. Ваше решение шикарное, полностью подходит. И еще прямо точно как в питоне реализовано! Спасибо большое!

Добавлено через 3 минуты
outoftime, спасибо большое! Очень красиво!

Новые блоги и статьи Все статьи Все блоги /
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .

Найти все сочетания с повторениями из букв A, B, C, D заданного размера

Решение

Решение

Решение

@Valeriiia 0 / 0 / 1 Регистрация: 01.07.2017 Сообщений: 22

	Найти все сочетания с повторениями из букв A, B, C, D заданного размера 29.01.2018, 15:31. Показов 7312. Ответов 18 Метки n, python, с, сочетания с повторениями (Все метки) Как написать следующую функцию на с++? def possible_variants(k): return [''.join(x) for x in product('ABCD', repeat=k)] То есть найти все сочетания с повторениями из букв A, B, C, D размером k. Например, при k=2: AA AB AC AD BB и т.д. 0

@GbaLog- Любитель чаепитий 3745 / 1801 / 566 Регистрация: 24.08.2014 Сообщений: 6,020 Записей в блоге: 1
	29.01.2018, 15:35
	del 0

@Valeriiia 0 / 0 / 1 Регистрация: 01.07.2017 Сообщений: 22
	29.01.2018, 15:40 [ТС]
	itertools.product(*iterables[, repeat]) Cartesian product of input iterables. Roughly equivalent to nested for-loops in a generator expression. For example, product(A, B) returns the same as ((x,y) for x in A for y in B). The nested loops cycle like an odometer with the rightmost element advancing on every iteration. This pattern creates a lexicographic ordering so that if the input’s iterables are sorted, the product tuples are emitted in sorted order. 0

@Valeriiia 0 / 0 / 1 Регистрация: 01.07.2017 Сообщений: 22
	29.01.2018, 16:20 [ТС]
	но эта программа не сработает, если k больше 4 )) (c повторениями же) 0

@Valeriiia 0 / 0 / 1 Регистрация: 01.07.2017 Сообщений: 22
	29.01.2018, 16:33 [ТС]
	это да) но нужно размера k, вот в чем загвоздка( 0

@Avaddon74 571 / 353 / 133 Регистрация: 15.09.2017 Сообщений: 1,239
	29.01.2018, 16:37
	Когда k больше 4-х то все сработает как k==4 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	29.01.2018, 22:15
	Сообщение было отмечено Valeriiia как решение Решение Valeriiia, перечитывая тему, закрались у меня сомнения. Порядок букв важен? То есть AABB и BBAA, ABBA - это разные комбинации? Если разные, тогда мое решение рулит. Если они все считаются за одну, тогда нужен другой алгоритм. Добавлено через 13 минут Тогда задача сводится к нахождению всех целых неотрицательных решений уравнения x1 + x2 + x3 + x4 = k Где-то на форуме такая задача уже была... Добавлено через 2 минуты Число таких комбинаций находится по формуле C_k+m-1^m-1, m=4 1

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	29.01.2018, 22:27
	Байт, вот дока питона, там есть псевдореализация product https://docs.python.org/3/libr... ls.product А вот описание того, что она делает: https://en.wikipedia.org/wiki/Cartesian_product 0

@Avaddon74 571 / 353 / 133 Регистрация: 15.09.2017 Сообщений: 1,239
	29.01.2018, 23:59
	alex white, Только сейчас заметил твой пример Чувствую себя копипастой ) 0

@Valeriiia 0 / 0 / 1 Регистрация: 01.07.2017 Сообщений: 22
	30.01.2018, 13:21 [ТС]
	Байт, порядок важен. Ваше решение шикарное, полностью подходит. И еще прямо точно как в питоне реализовано! Спасибо большое! Добавлено через 3 минуты outoftime, спасибо большое! Очень красиво! 0