THIS IS NOT A NORMAL COMBINATION! We need an algorithm that generates the values ​​of possible combinations of 2 elements (I will be glad to any number), which are used strictly a certain number of times - no more, no less. Roughly speaking, the algorithm places a certain amount of a given element with all possible options. For example, I give the function call and the result of the work in the array:

combination(8,4){ //8 - длина строки для размещения 4 элементов //код }

result in array:

 array[]={ 00001111, 00010111, 00011011, 00011101, ..., 11110000}

For a better understanding, I give a link to the online calculated options - http://integraloff.net/TepBep/cnk.php , enter the value 8 and 4 there.

  • and what you are not satisfied with frontal recursion? What are the restrictions on N and K? - pavel
  • brute force ALL possible combinations are not satisfied, because In this version, it is necessary that in each row there are four 0 and four 1 - Arsen Kul
  • I understand what you want to do. What exactly did you fail? Or works too long? - pavel
  • I tried different options. Faithful could neither write nor find on the Internet. Of course, I know the brute-way - go through ALL the options and extract the necessary strings from them ififs - Arsen Kul

2 answers 2

Here is the simplest version in C ++ (almost nothing depends on the language here). The idea is almost the same as in the generation of the following permutation of elements.

 bool next_combination (vector<int> & a) { int C1 = 0; for (int i = a.size() - 1; i>=0; i--) if (a[i]) C1++; else if (C1){ a[i] = 1; for (int j=a.size() -1; j > i; j--) a[j] = (--C1 > 0); return true; } return false; } int main() { vector<int> P = {0,0,0,1,1}; do { for (auto x: P) cout << x<< " "; cout << endl; cin.get(); } while (next_combination(P)); }
  • How much is a vector in C ++ replaced with an array in Java? - Arsen Kul
  • @ ArsenKul here completely. Only its size is used. - pavel
  • hmm, in C ++ return can return several times the result in just one call? And, as I understand it, true = 1, false = 0? It seems so easy in Java not to realize ... after all, only 1 return to the call. - Arsen Kul
  • Hmm ... there is also 1 return per call. 1/0 true / false as you prefer - pavel
  • Replaced all labor / falls on 1/0. Despite the complete external similarity, the algorithm does not reach the internal loop, but falls into an endless pang. Maybe I somehow incorrectly converted the code? Please rewrite the code: if (a [i]) C1 ++; else if (C1) {a [i] = 1; for (int j = a.size () -1; j> i; j--) a [j] = (--C1> 0); return true; } return false; so that there are numbers and not boolean - Arsen Kul

The problem is easily solved by recursion. For example, so.

Note that all combinations of n by k are obtained as follows: these are combinations of (n - 1) for k with zero assigned at the end, plus combinations of (n - 1) for (k - 1) with a unit assigned at the end.

Hence the code (C #):

 IEnumerable<List<int>> Combinations(int n, int k) { if (k < 0 || k > n) yield break; if (n <= 0) { yield return new List<int>(); yield break; } foreach (var res in Combinations(n - 1, k)) { res.Add(0); yield return res; } foreach (var res in Combinations(n - 1, k - 1)) { res.Add(1); yield return res; } }
  • the result would be cached, but the complexity is too terrible ... - pavel
  • look at my answer, I feel my back that I can speed it up to O (1) for 1 combination ... - pavel
  • why not? roughly speaking we cut off [01] [10] and the same thing we recalculate further (n-2, k-1) - pavel
  • @pavel: Well, the total number of operations is 2 * C_n ^ k (it is proved recursively), so there are no particularly large losses? - VladD 2:49 pm
  • Unfortunately, C # do not know. I need to somehow rewrite to Java, but I don’t know what the yield is. And I use not a list, but a simple array. Like in Java, Integer can be sorted out by foriche, but it doesn’t matter, for me it’s already the little things in life. - Arsen Kul