RcdMathLib_doc
Open Source Library for Linear and Non-linear Algebra
combinatorics.c
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2020 Zakaria Kasmi <zkasmi@inf.fu-berlin.de>
3  * 2020 Freie Universität Berlin
4  *
5  * This file is subject to the terms and conditions of the GNU Lesser General
6  * Public License v2.1. See the file LICENSE in the top level directory for more
7  * details.
8  */
9 
23 #include <stdio.h>
24 #include <stdlib.h>
25 
26 #include "combinatorics.h"
27 #include "vector.h"
28 
29 uint8_t combinatorics_init(uint8_t n, uint8_t k, uint8_t comb_arr[])
30 {
31  if (k > n) {
32  return (COMBI_ERROR);
33  }
34 
35  if (k == 0) {
36  return (COMBI_EMPTY);
37  }
38 
39 
40  // Initialization of the combinatoric array with k-values.
41  for (uint32_t i = 0; i < k; i++) {
42  comb_arr[i] = i;
43  }
44 
45  return (COMBI_SUCCESS);
46 }
47 
48 uint8_t combinatorics_get_next_without_rep(uint8_t n, uint8_t k,
49  uint8_t comb_arr[])
50 {
51 
52  if (comb_arr[k - 1] < n - 1) {
53  comb_arr[k - 1] = comb_arr[k - 1] +1;
54  return (COMBI_SUCCESS);
55  }
56 
57  int32_t i;
58  for (i = k - 2; i >= 0; i--) {
59  if (comb_arr[i] < n - k + i) {
60  break;
61  }
62  }
63 
64  //Break, if comb_arr[0] == n - k
65  if (i < 0) {
66  return (COMBI_END);
67  }
68 
69  comb_arr[i] = comb_arr[i] + 1;
70 
71  while (i < k - 1) {
72  comb_arr[i + 1] = comb_arr[i] + 1;
73  i++;
74  }
75 
76  return (COMBI_SUCCESS);
77 }
COMBI_EMPTY
#define COMBI_EMPTY
Case of an empty combination set.
Definition: combinatorics.h:36
COMBI_ERROR
#define COMBI_ERROR
Case of an error.
Definition: combinatorics.h:31
combinatorics.h
Calculate possible without repetition in ascending order.
COMBI_SUCCESS
#define COMBI_SUCCESS
Case of successfully calculated combination set.
Definition: combinatorics.h:41
COMBI_END
#define COMBI_END
Case of completion of calculating combination sets.
Definition: combinatorics.h:46
vector.h
Vector computations.
combinatorics_init
uint8_t combinatorics_init(uint8_t n, uint8_t k, uint8_t comb_arr[])
Initialize the combinations generator.
Definition: combinatorics.c:29
combinatorics_get_next_without_rep
uint8_t combinatorics_get_next_without_rep(uint8_t n, uint8_t k, uint8_t comb_arr[])
Generate the next combination.
Definition: combinatorics.c:48