Вычислить количество возможных комбинаций

@tdo22 · Регистрация: 14.02.2013

Здравствуйте,
есть массив типа int который создается и заполняется динамически, его максимальной размер может быть 256.
Для примера пусть будет такой:

C++
1
2
int arr_size = 3;
int i[arr_size] = {252, 254, 255};

мне нужно посчитать сколько раз нужно увеличивать цифры чтоб получить максимальные значение,
то-есть 254 255 256.
Не знаю правильно ли я пояснил что мне нужно, но если расписать "вручную", то это выглядит так:

C++
1
2
3
4
5
6
7
252 254 255
252 254 256
252 255 256
253 254 255
253 254 256
253 255 256
254 255 256

получается что из данного примера мне нужна цифра 7, так как из 252 254 255 до 254 255 256 - 7 комбинаций.
В реальности массив намного больше, по-этому нужно алгоритм который будет быстро работать.

Байт · 17.02.2015, 18:50

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

мне нужен алгоритм который посчитает количество комбинаций математически,

Пусть есть K чисел a1 < a2 < a3. Дополним K+1-м числом a4 = M (максимум+1, в данном примере = 257=256+1)
Последнее число можно изменять в пределах от a3 до М-1 - имеем a4 - a3 + 1 варианта. = С¹_a4-a3 + 1
Меняем последние 2 числа. Количество вариантов здесь это количество выборов по 2 числа из отрезка a2+1 -- a4-1 = C²_a4-a2-2
Меняем последние 3 числа. Вариантов выбрать 3 числа из отрезка a1+1 -- a4-1 = C³_a4-a1-2.
Так. Закономерность уже проглядывается.
Далее все это складывается.
Попробуйте обобщить это хозяйство на произвольное количество.
Видимо, если внизу биномального коэфициэнта окажется нечто <=0, его надо считать равным нулю.
Прошу прощения за некую сумбурность, просто стенографировал собственные мысли.
Фишка в том, что если есть отрезок n чисел и нам надо получить из них возрастающие последовательности из k чисел, то этих последовательностей будет ровно C_n^k
Пример. Последовательность 250 251 252 253 254 255 256 (n=7). Нужно выбрать k=4 числа. Способов C⁷⁴

@NotNot · 18.02.2015, 12:26

tdo22, оно?

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
#include <algorithm> // std::iota
#include <iostream>
#include <vector>
#include <stack>
 
using uint     = unsigned int;
using uint_vec = std::vector<uint>;
 
uint count_recurse(const uint_vec & vec, uint index, uint state_count) {
  if (vec.size() < 2)
    return vec.size();
 
  uint count = 0u;
 
  auto count_state = [&vec] (uint i, uint x) {
    return x - vec[i];
  };
 
  auto at_state = [&vec] (uint i, uint j) {
    return vec[i] + j;
  };
 
  for (auto state = 0u; state < state_count; ++state) {
    if (index == 0)
      count += count_state(0, at_state(index + 1, state));
    else
      count += count_recurse(vec, index - 1, count_state(index, at_state(index + 1, state)));
  }
 
  return count;
}
 
uint count_non_recurse(const uint_vec & vec, uint max) {
  if (vec.size() < 2)
    return vec.size();
 
  auto count_state = [&vec] (uint i, uint x) {
    return x - vec[i];
  };
 
  auto at_state = [&vec] (uint i, uint j) {
    return vec[i] + j;
  };
 
  uint count = 0u;
 
  std::stack<uint> index_st;
  std::stack<uint> state_st;
  std::stack<uint> state_count_st;
 
  index_st.push(vec.size() - 2);
  state_st.push(max - vec.back() + 1);
 
  auto state = 0u;
 
  do {
    while (state < state_st.top()) {
      if (index_st.top() == 0) {
        count += count_state(0, at_state(index_st.top() + 1, state));
      } else {
        state_st.push(count_state(index_st.top(), at_state(index_st.top() + 1, state)));
        index_st.push(index_st.top() - 1);
        state_count_st.push(state);
        state = 0u;
        break;
      }
 
      ++state;
    }
 
    if (state == state_st.top()) {
      index_st.pop();
      state_st.pop();
 
      if (!state_count_st.empty()) {
        state = state_count_st.top() + 1;
        state_count_st.pop();
      }
    }
  } while (!index_st.empty());
 
  return count;
}
 
int main(int, char * []) {
  uint_vec values (256);
  uint max = 256;
 
  std::iota(values.begin(), values.end(), 0u);
 
  uint rcount  = count_recurse(values, values.size() - 2, max - values.back() + 1);
  uint nrcount = count_non_recurse(values, max);
 
  std::cout << "recursive:     " << rcount  << '\n'
            << "non recursive: " << nrcount << '\n';
}

Добавлено через 17 минут
Накосячил немного, нужно так

Кликните здесь для просмотра всего текста

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
102
103
104
105
106
107
108
109
110
#include <algorithm> // std::iota
#include <iostream>
#include <vector>
#include <stack>
 
using uint     = unsigned int;
using uint_vec = std::vector<uint>;
 
uint count_recurse_impl(const uint_vec & vec, uint index, uint state_count) {
  uint count = 0u;
 
  // кол-во состояний i-го элемента. x - это i + 1 элемент
  auto count_state = [&vec] (uint i, uint x) {
    return x - vec[i];
  };
 
  // j-ое состояние i-го элемента
  auto at_state = [&vec] (uint i, uint j) {
    return vec[i] + j;
  };
 
  for (auto state = 0u; state < state_count; ++state) {
    if (index == 0)
      count += count_state(0, at_state(index + 1, state));
    else
      count += count_recurse_impl(vec, index - 1, count_state(index, at_state(index + 1, state)));
  }
 
  return count;
}
 
uint count_recurse(const uint_vec & vec, uint max) {
  if (vec.size() < 2) {
    if (vec.size())
      return max - vec.back() + 1;
    return 0;
  }
 
  return count_recurse_impl(vec, vec.size() - 2, max - vec.back() + 1);
}
 
uint count_non_recurse(const uint_vec & vec, uint max) {
  if (vec.size() < 2) {
    if (vec.size())
      return max - vec.back() + 1;
    return 0;
  }
 
  // кол-во состояний i-го элемента. x - это i + 1 элемент
  auto count_state = [&vec] (uint i, uint x) {
    return x - vec[i];
  };
 
  // j-ое состояние i-го элемента
  auto at_state = [&vec] (uint i, uint j) {
    return vec[i] + j;
  };
 
  uint count = 0u;
 
  std::stack<uint> index_st;
  std::stack<uint> state_st;
  std::stack<uint> state_count_st;
 
  index_st.push(vec.size() - 2);
  state_st.push(max - vec.back() + 1);
 
  auto state = 0u;
 
  do {
    while (state < state_st.top()) {
      if (index_st.top() == 0) {
        count += count_state(0, at_state(index_st.top() + 1, state));
      } else {
        state_st.push(count_state(index_st.top(), at_state(index_st.top() + 1, state)));
        index_st.push(index_st.top() - 1);
        state_count_st.push(state);
        state = 0u;
        break;
      }
 
      ++state;
    }
 
    if (state == state_st.top()) {
      index_st.pop();
      state_st.pop();
 
      if (!state_count_st.empty()) {
        state = state_count_st.top() + 1;
        state_count_st.pop();
      }
    }
  } while (!index_st.empty());
 
  return count;
}
 
int main(int, char * []) {
  uint_vec values (256);
  uint max = 256;
 
  std::iota(values.begin(), values.end(), 0u);
 
  uint rcount  = count_recurse(values, values.size() - 2, max - values.back() + 1);
  uint nrcount = count_non_recurse(values, max);
 
  std::cout << "recursive:     " << rcount  << '\n'
            << "non recursive: " << nrcount << '\n';
}

Байт · 18.02.2015, 13:01

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#define N 3
#define M 256
 
main()
{ // int a[N] = {251, 254, 256 };
  int a[N] = {252, 254, 255 };
  int s, ix, i, n, k, j, C;
 
s = 1;
for(ix=N-1, i=0; ix>=0; ix--, i++)
  if (a[ix] < M - i) break;
for(i=ix; i>=0; i--) {
  n = M - a[i];  // Кол-во "мест"
  k = N - i;    // Кол-во "фишек"
   //printf("i=%d n=%d k=%d ix=%d\n", i, n, k, ix);
  for(j=k+1, C=1; j<=n; j++) C *= j;  // Вычисление C(n,k)
  for(j=2; j<=n-k; j++) C /= j;
  s += C;
}
printf("s=%d\n", s);
}

Проверьте, кому не лень. Для исходных чисел у меня получилось 7. Для закоментаренных 12.

@NotNot · 18.02.2015, 13:15

Байт, для закомментированных должно получиться 7

Байт · 18.02.2015, 13:18

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

для закомментированных должно получиться 7

1 4 6
1 5 6
2 3 4
2 3 5
2 3 6
2 4 5
2 4 6
2 5 6
3 4 5
3 4 6
3 5 6
4 5 6
А вы как считали?

@NotNot · 18.02.2015, 13:22

Байт, числа не могут стать меньше чем были изначально же

1 4 6
2 4 6
3 4 6
1 5 6
2 5 6
3 5 6
4 5 6

Байт · 18.02.2015, 13:27

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

Байт, числа не могут стать меньше чем были изначально же

Прошу прощения. Неправильно интерпретировал условие. Думаю, что это даже проще. Но чуть погодя.

Новые блоги и статьи Все статьи Все блоги /
[golang] Pipeline alhaos 08.06.2026 Pipeline Pipeline — паттерн конкурентной обработки данных в Go. Суть: данные проходят через цепочку независимых стадий, каждая из которых работает в своей горутине и общается с соседями через. . .	Свет внутри себя kumehtar 07.06.2026 Пусть это будет здесь lIs4oanZS9Y	Программа для com-порта Uhbif79 05.06.2026 Всем привет, давно хотел изучить Qt, начинал, бросал, потом снова начинал. И сейчас вот смог написать свою первую программу. До этого имел опыт программирования микроконтроллеров, писал прошивки на. . .	Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[ anaschu 01.06.2026 Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .
21 мат мед. Планы на развитие модели здравоСохранения anaschu 01.06.2026 AnyLogic: план развития симуляционной модели рабочего коллектива — динамический абсентеизм, реальные данные, три сценария сравнения Продолжаю серию постов о дискретно-событийной модели рабочего. . .	20. Мат мед. Абсентеизм как отдельный тип простоя anaschu 29.05.2026 Апдейт модели: исправленные баги, абсентеизм и новые механизмы Продолжаю развивать ранее описанную модель рабочего коллектива на AnyLogic. За последние несколько дней был проведён серьёзный. . .	19. здоровье, усталость и психотип работника влияют на производительность предприятия, и наоборот, производительность на здоровье, усталось и психотип anaschu 28.05.2026 Дискретно-событийная модель рабочего коллектива на AnyLogic: здоровье, выгорание, психотипы и микростимуляция Привет, коллеги. Хочу поделиться итогами нескольких недель работы над симуляционной. . .	"Прокси" для последовательного порта Eddy_Em 28.05.2026 Эту штуку написал я достаточно давно. Но сейчас вот понадобилось настроить датчик грозы, но при этом не отключать его от "метеодемона". Соответственно, надо запустить этот "прокси": метеодемон будет. . .

@NotNot 31 / 31 / 6 Регистрация: 23.10.2014 Сообщений: 107
	18.02.2015, 13:15
	Байт, для закомментированных должно получиться 7 0

@NotNot 31 / 31 / 6 Регистрация: 23.10.2014 Сообщений: 107
	18.02.2015, 13:22
	Байт, числа не могут стать меньше чем были изначально же 1 4 6 2 4 6 3 4 6 1 5 6 2 5 6 3 5 6 4 5 6 1