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 <stdlib.h>
#include "util.h"
int cmpint(const void *p1, const void *p2) {
return *(int*)p1 - *(int*)p2;
}
void quicksort(int *data, int start, int end) {
qsort(&data[start], end-start+1, sizeof(int), cmpint);
}
void reverse(int *data, int start, int end) {
int temp;
while (start < end) {
temp = data[start];
data[start] = data[end];
data[end] = temp;
start++; end--;
}
}
void permute(int *data, int count) {
int i, p, t;
for (i = count-1; i >= 0; i--) {
p = (int) ((i+1) * (rand() / (RAND_MAX + 1.0)));
t = data[i];
data[i] = data[p];
data[p] = t;
}
}
void result_add(struct result_node **list, int value) {
// make sure we have a list
if (*list == NULL) {
*list = (struct result_node *)malloc(sizeof(struct result_node));
(*list)->value = value;
(*list)->prob = 1;
(*list)->next = NULL;
return;
}
// walk the list
struct result_node *cur = *list, *last = NULL;
while ((cur != NULL) && (cur->value < value)) {
last = cur;
cur = cur->next;
}
// see what we have to do
if (cur == NULL) {
cur = (struct result_node *)malloc(sizeof(struct result_node));
cur->value = value;
cur->prob = 1;
cur->next = NULL;
last->next = cur;
return;
}
else if (cur->value == value) {
cur->prob++;
return;
}
else if (last != NULL) {
last->next = (struct result_node *)malloc(sizeof(struct result_node));
last->next->value = value;
last->next->prob = 1;
last->next->next = cur;
}
else {
*list = (struct result_node *)malloc(sizeof(struct result_node));
(*list)->value = value;
(*list)->prob = 1;
(*list)->next = cur;
}
}
inline void swapperm(int *data, int i, int j) {
if (i == j)
return;
data[i] ^= data[j];
data[j] ^= data[i];
data[i] ^= data[j];
};
void _rec_all_permutations(int *data, int count,
void (*callback)(int *data, int count, void *arg, float farg),
void *arg, float farg, int n) {
if (1 == n) {
callback(data, count, arg, farg);
}
else {
int c;
for (c = 0; c < n; c++) {
_rec_all_permutations(data, count, callback, arg, farg, n-1);
swapperm(data, n%2 == 1 ? 0 : c, n-1);
}
}
}
void all_permutations(int *data, int count,
void (*callback)(int *data, int count, void *arg, float farg),
void *arg, float farg) {
_rec_all_permutations(data, count, callback, arg, farg, count);
}
long factorial(int n) {
long fact = 1;
while (n > 0) {
fact *= n--;
}
return fact;
}
|
