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

@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

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

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

Новые блоги и статьи Все статьи Все блоги /
Хабру пора сливаться, время пришло, оно прийдёт за всеми, но ему давно пора (Хабр - галимый плагиат и кликбейт с саморекламой). Hrethgir 04.08.2026 Стирают публикации с эффективными алгоритмами (в частности по алгоритму обхода дерева, был опубликован там 3-го мая, в зипапке . . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .	Почему SEO не начинается с ключевых слов: что проверить до написания текстов Neotwalker 01.08.2026 Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .	Знание — сила: Доктрина интенциональности знаний, углубление в формулу Hrethgir 01.08.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11957&stc=1&d=1785567302 Знаменитый афоризм Фрэнсиса Бэкона «Знание — сила» (Scientia potentia est) в массовой культуре принято понимать. . .

@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

Опции темы