## Combinatorics with constraint

**Moderators:** gmalivuk, Moderators General, Prelates

### Combinatorics with constraint

Hi,

I need your help

Let A be a set of integers numbers {1,2,3,....,n}

I want to extract combinations of k-uples such as no combination shares pairwise more than 2 numbers.

What is the maximal number of k-uples I could extract satisfying the condition above ?

n=10

k=5

It is easy to know how many 5-uples I could extract :

C(10,5)=252

But how to find among those 252 quintuples the 5-uples sharing pairwise at most 2 numbers?

6 or more?

Is there a general formula to find such maximal number?

Is there an algorithm finding such combinations?

I want to know more exactly the value of this maximum for :

n=50

k=10

Thank you for any clue

I need your help

Let A be a set of integers numbers {1,2,3,....,n}

I want to extract combinations of k-uples such as no combination shares pairwise more than 2 numbers.

What is the maximal number of k-uples I could extract satisfying the condition above ?

n=10

k=5

It is easy to know how many 5-uples I could extract :

C(10,5)=252

But how to find among those 252 quintuples the 5-uples sharing pairwise at most 2 numbers?

6 or more?

Is there a general formula to find such maximal number?

Is there an algorithm finding such combinations?

I want to know more exactly the value of this maximum for :

n=50

k=10

Thank you for any clue

### Re: Combinatorics with constraint

I don't know anything for certain about exact values, but the biggest set of such 5-tuples I can find out of 10 numbers is given by the rows of the following matrix:

And I can get a rough upper bound for arbitrary n and k as follows:

Define a graph G whose nodes are the k-tuples. Connect two k-tuples by an edge if they have k-1 elements in common.

Then if two k-tuples have exactly h elements in common, they are at distance k-h from each other. In particular, two k-tuples have at most 2 elements in common if they are at distance at least k-2 from each other.

Now we can associate with each k-tuple x a set N(x) of k-tuples that are at distance at most (k-3)/2 from x. Include x in N(x). Then a set S of k-tuples that are at distance at least k-2 from each other will produce a set of sets {{N(x): x in S} that don't overlap each other. Each set N(x) is of the same size M. Then we know S has at most floor(C(n,k)/M) elements.

I expect this to be a better bound for odd k than for even k.

We can calculate M by adding the numbers of sets at the appropriate distances from a tuple x.

Distance 0: 1

Distance 1: k*(n-k)

Distance 2: c(k,2)*c(n-k,2)

..

Distance d: c(k,d)*c(n-k,d)

....

For k odd: Distance (k-3)/2: c(k,(k-3)/2)*c(n-k,(k-3)/2)

For k even: Distance (k-4)/2: c(k,(k-4)/2)*c(n-k,(k-4)/2)

Now for n=10, k=5, M=1+5*5 = 26, so S has at most floor(C(10,5)/26) = 9 elements. Not a great bound, if 6 is really the maximum size, but a lot better than 252.

For n=50, k=10, M = 1+10*40+45*780+120*9880 = 1221101, and C(50,10) is about 1.0272e+010, so the upper bound is about 8412.

Code: Select all

`b =`

1 1 1 1 1 0 0 0 0 0

1 0 0 0 1 1 1 1 0 0

1 1 0 0 0 0 0 1 1 1

0 1 1 0 0 1 1 0 0 1

0 0 0 1 1 1 0 0 1 1

0 0 1 1 0 0 1 1 1 0

And I can get a rough upper bound for arbitrary n and k as follows:

Define a graph G whose nodes are the k-tuples. Connect two k-tuples by an edge if they have k-1 elements in common.

Then if two k-tuples have exactly h elements in common, they are at distance k-h from each other. In particular, two k-tuples have at most 2 elements in common if they are at distance at least k-2 from each other.

Now we can associate with each k-tuple x a set N(x) of k-tuples that are at distance at most (k-3)/2 from x. Include x in N(x). Then a set S of k-tuples that are at distance at least k-2 from each other will produce a set of sets {{N(x): x in S} that don't overlap each other. Each set N(x) is of the same size M. Then we know S has at most floor(C(n,k)/M) elements.

I expect this to be a better bound for odd k than for even k.

We can calculate M by adding the numbers of sets at the appropriate distances from a tuple x.

Distance 0: 1

Distance 1: k*(n-k)

Distance 2: c(k,2)*c(n-k,2)

..

Distance d: c(k,d)*c(n-k,d)

....

For k odd: Distance (k-3)/2: c(k,(k-3)/2)*c(n-k,(k-3)/2)

For k even: Distance (k-4)/2: c(k,(k-4)/2)*c(n-k,(k-4)/2)

Now for n=10, k=5, M=1+5*5 = 26, so S has at most floor(C(10,5)/26) = 9 elements. Not a great bound, if 6 is really the maximum size, but a lot better than 252.

For n=50, k=10, M = 1+10*40+45*780+120*9880 = 1221101, and C(50,10) is about 1.0272e+010, so the upper bound is about 8412.

### Re: Combinatorics with constraint

Thank you for your comment.

In fact it is not easy to compute the maximal possible number of combinations under such constraint.

I have a question anyway.

If we use the algorithm below to simulate such value (or at least to near it) can we succeed?

I assume that for some n and k we make an exhaustive research.

Algorithm for n=50 k=10

1. We pick randomly a set of 10 numbers

2. We store it

3. We continue picking sets of 10 out of 50 while comparing them pairwise.

4. If the combinations of 10 uples share pairwise at most 2 we accept them Otherwise we go for another try

5. We run the program until some number of 10 uples picked (to define) give no combination to add.

6. After a number of iteration of the same process we will have many reached values. We then choose the maximal value

Question : will this algorithm give a value nearing the "computed" maximum?

For n=18 and k=5 for example the maximal number is 68

Does the algorithm help us to reach 68 or a number slightly < 68?

In fact it is not easy to compute the maximal possible number of combinations under such constraint.

I have a question anyway.

If we use the algorithm below to simulate such value (or at least to near it) can we succeed?

I assume that for some n and k we make an exhaustive research.

Algorithm for n=50 k=10

1. We pick randomly a set of 10 numbers

2. We store it

3. We continue picking sets of 10 out of 50 while comparing them pairwise.

4. If the combinations of 10 uples share pairwise at most 2 we accept them Otherwise we go for another try

5. We run the program until some number of 10 uples picked (to define) give no combination to add.

6. After a number of iteration of the same process we will have many reached values. We then choose the maximal value

Question : will this algorithm give a value nearing the "computed" maximum?

For n=18 and k=5 for example the maximal number is 68

Does the algorithm help us to reach 68 or a number slightly < 68?

### Re: Combinatorics with constraint

For the values n=50 k=10 I obtained an upper bound of 61 combinations of 10-uples.

I have to test it using my algorithm above (picking randomly set of 10-uples and sieving it to see if I could find more than 61).

I used a formula (I`m not sure of 100%) that is why I did not publish it for now.

n=10 k=5 the upper bound is 7 and the maximum is 6.

n=18 k=5 the upper bound is 87 and the maximum is 68

n=50 k=5 the upper bound is 3040 and the maximum unknown for now.

I have to test it using my algorithm above (picking randomly set of 10-uples and sieving it to see if I could find more than 61).

I used a formula (I`m not sure of 100%) that is why I did not publish it for now.

n=10 k=5 the upper bound is 7 and the maximum is 6.

n=18 k=5 the upper bound is 87 and the maximum is 68

n=50 k=5 the upper bound is 3040 and the maximum unknown for now.

### Re: Combinatorics with constraint

My formula is derived from a very simple idea.

An example with n=10 k=5

Any 5-uple sharing 0,1 or 2 numbers with others is a "candidate".

If we start with 1-2-3-4-5

we have one combination sharing 0 number with 1-2-3-4-5 (6-7-8-9-10)

we have 25 combinations sharing 1 number with 1-2-3-4-5 (C(5,1)*C(5,4))

we have 100 combinations sharing 2 numbers with 1-2-3-4-5 (C(5,2)*C(5,3))

So we have 1+25+100=126 combinations possible if we start from any 5-uple

Hence we have 1 out 2 possible. Let us note this ratio 1/2 "t" and "r" (r=1/t)

The upper bound M will be then for n and k :

M=int(ln(C(n,k))/ln(r))

(where "int" is the integer part)

Is my formula right or wrong?

An example with n=10 k=5

Any 5-uple sharing 0,1 or 2 numbers with others is a "candidate".

If we start with 1-2-3-4-5

we have one combination sharing 0 number with 1-2-3-4-5 (6-7-8-9-10)

we have 25 combinations sharing 1 number with 1-2-3-4-5 (C(5,1)*C(5,4))

we have 100 combinations sharing 2 numbers with 1-2-3-4-5 (C(5,2)*C(5,3))

So we have 1+25+100=126 combinations possible if we start from any 5-uple

Hence we have 1 out 2 possible. Let us note this ratio 1/2 "t" and "r" (r=1/t)

The upper bound M will be then for n and k :

M=int(ln(C(n,k))/ln(r))

(where "int" is the integer part)

Is my formula right or wrong?

### Re: Combinatorics with constraint

Here are some values :

First column : n

Second column : k

Third column : M the upper bound

50 5 3040

49 5 2841

48 5 2650

47 5 2469

46 5 2297

45 5 2133

44 5 1977

43 5 1829

42 5 1689

41 5 1557

40 5 1432

39 5 1314

38 5 1203

37 5 1098

36 5 1000

35 5 908

34 5 823

33 5 742

32 5 668

31 5 599

30 5 535

29 5 475

28 5 421

27 5 371

26 5 325

25 5 283

24 5 245

23 5 211

22 5 180

21 5 152

20 5 127

19 5 106

18 5 87

17 5 70

16 5 56

15 5 43

14 5 33

13 5 24

12 5 17

11 5 12

10 5 7

We could find an exact formula by correcting the upper bound M.

So if we note M` the maximal number of combinations we will have :

M`=M*c

c is always 0.5<=c< 1

where c is the correction factor

c depends on the size of n

The only way to find an explicit formula for c is to compute c for few values from n=10 to 25 for example and then to analyze the behavior of c.

Finding the combinations is more harder problem.

I had the theoretical solution but I do not know how to extract a maximal sub matrix filled only with 1`s from a large matrix (symmetrical binary (0 and 1`s). Someone told me in another forum that it is doable without explaining more.

First column : n

Second column : k

Third column : M the upper bound

50 5 3040

49 5 2841

48 5 2650

47 5 2469

46 5 2297

45 5 2133

44 5 1977

43 5 1829

42 5 1689

41 5 1557

40 5 1432

39 5 1314

38 5 1203

37 5 1098

36 5 1000

35 5 908

34 5 823

33 5 742

32 5 668

31 5 599

30 5 535

29 5 475

28 5 421

27 5 371

26 5 325

25 5 283

24 5 245

23 5 211

22 5 180

21 5 152

20 5 127

19 5 106

18 5 87

17 5 70

16 5 56

15 5 43

14 5 33

13 5 24

12 5 17

11 5 12

10 5 7

We could find an exact formula by correcting the upper bound M.

So if we note M` the maximal number of combinations we will have :

M`=M*c

c is always 0.5<=c< 1

where c is the correction factor

c depends on the size of n

The only way to find an explicit formula for c is to compute c for few values from n=10 to 25 for example and then to analyze the behavior of c.

Finding the combinations is more harder problem.

I had the theoretical solution but I do not know how to extract a maximal sub matrix filled only with 1`s from a large matrix (symmetrical binary (0 and 1`s). Someone told me in another forum that it is doable without explaining more.

- gmalivuk
- GNU Terry Pratchett
**Posts:**26441**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: Combinatorics with constraint

Dude, you can edit posts to add additional information. Please don't post 3 or 4 times in a row.

### Re: Combinatorics with constraint

A distinction is usually drawn between "Maximal", meaning cannot be extended to something larger, and "Maximum", meaning nothing larger exists. Finding a maximal square submatrix of all "1"s in a symmetric 0-1 matrix is pretty easy -- the greedy algorithm will work. Finding a maximum such submatrix, on the other hand, is essentially the Maximum Clique problem, the decision problem version of which is one of the classic NP-complete problems. That is, not so easy.

### Re: Combinatorics with constraint

DavidSh wrote:A distinction is usually drawn between "Maximal", meaning cannot be extended to something larger, and "Maximum", meaning nothing larger exists. Finding a maximal square submatrix of all "1"s in a symmetric 0-1 matrix is pretty easy -- the greedy algorithm will work. Finding a maximum such submatrix, on the other hand, is essentially the Maximum Clique problem, the decision problem version of which is one of the classic NP-complete problems. That is, not so easy.

Thank you for the clarification.

So the guy was for sure thinking to the greedy algorithm.

For n=50 k=10 I reached 30 combinations of 10-uples but it is quite sure that it is no the maximal number.

### Re: Combinatorics with constraint

Here is a result :

n=15 k=5

My formula (see above) gave an upper bound of 43

There are 42 combinations sharing pairwise at most 2 numbers.

Here is the list (checked by me) of 42 combinations :

1 2 3 7 8

1 2 4 5 6

1 2 9 10 11

1 2 12 13 14

1 3 4 9 12

1 3 5 10 13

1 3 6 14 15

1 4 7 10 14

1 4 11 13 15

1 5 7 9 15

1 5 8 11 14

1 6 7 11 12

1 6 8 9 13

1 8 10 12 15

2 3 4 10 15

2 3 5 9 14

2 3 6 11 13

2 4 7 9 13

2 4 8 11 12

2 5 7 10 12

2 5 8 13 15

2 6 8 10 14

2 6 9 12 15

2 7 11 14 15

3 4 5 7 11

3 4 8 13 14

3 5 6 8 12

3 6 7 9 10

3 7 12 13 15

3 8 9 11 15

3 10 11 12 14

4 5 8 9 10

4 5 12 14 15

4 6 7 8 15

4 6 9 11 14

4 6 10 12 13

5 6 7 13 14

5 6 10 11 15

5 9 11 12 13

7 8 9 12 14

7 8 10 11 13

9 10 13 14 15

The list was obtained using my theoretical solution (extracting a squared sub matrix from a large matrix).

n=15 k=5

My formula (see above) gave an upper bound of 43

There are 42 combinations sharing pairwise at most 2 numbers.

Here is the list (checked by me) of 42 combinations :

1 2 3 7 8

1 2 4 5 6

1 2 9 10 11

1 2 12 13 14

1 3 4 9 12

1 3 5 10 13

1 3 6 14 15

1 4 7 10 14

1 4 11 13 15

1 5 7 9 15

1 5 8 11 14

1 6 7 11 12

1 6 8 9 13

1 8 10 12 15

2 3 4 10 15

2 3 5 9 14

2 3 6 11 13

2 4 7 9 13

2 4 8 11 12

2 5 7 10 12

2 5 8 13 15

2 6 8 10 14

2 6 9 12 15

2 7 11 14 15

3 4 5 7 11

3 4 8 13 14

3 5 6 8 12

3 6 7 9 10

3 7 12 13 15

3 8 9 11 15

3 10 11 12 14

4 5 8 9 10

4 5 12 14 15

4 6 7 8 15

4 6 9 11 14

4 6 10 12 13

5 6 7 13 14

5 6 10 11 15

5 9 11 12 13

7 8 9 12 14

7 8 10 11 13

9 10 13 14 15

The list was obtained using my theoretical solution (extracting a squared sub matrix from a large matrix).

### Re: Combinatorics with constraint

for n=10, k=5, this works:

2 3 5 6 8

1 2 4 5 7

1 3 4 6 10

5 6 7 9 10

2 4 8 9 10

1 3 7 8 9

For more information, go to https://www.ccrwest.org/cover.html

In particular the page https://www.ccrwest.org/cover/t_pages/t ... _10_2.html contains this:

C(50,10,2) = 30

Created by Colin Barker

Method of Construction: Constructed using Simulated Annealing

1 2 3 4 5 6 7 8 9 10

1 9 11 13 19 24 25 31 33 47

1 9 12 14 21 27 28 29 43 48

1 9 15 17 20 22 23 26 40 50

1 9 16 30 34 35 37 42 45 46

1 9 18 32 36 38 39 41 44 49

2 5 11 25 26 27 28 32 38 46

2 5 12 15 16 19 22 24 44 49

2 5 13 14 23 36 41 42 45 50

2 5 17 18 21 34 35 39 47 48

2 5 20 29 30 31 33 37 40 43

3 6 11 15 21 22 25 42 45 48

3 6 12 26 31 33 34 35 36 41

3 6 13 16 18 20 27 28 39 40

3 6 14 17 19 24 30 32 37 38

3 6 23 29 43 44 46 47 49 50

4 8 12 13 14 16 17 26 46 47

4 11 12 18 23 25 30 37 39 50

4 13 15 22 29 32 34 35 38 43

4 17 27 28 31 33 42 44 45 49

4 19 20 21 24 36 40 41 46 48

7 10 11 16 17 25 29 36 41 43

7 10 12 20 32 38 40 42 45 47

7 10 13 21 26 30 37 44 48 49

7 10 14 15 18 22 31 33 39 46

7 10 19 23 24 27 28 34 35 50

8 11 14 20 25 34 35 40 44 49

8 15 22 27 28 30 36 37 41 47

8 16 21 23 31 32 33 38 48 50

8 18 19 24 26 29 39 42 43 45

2 3 5 6 8

1 2 4 5 7

1 3 4 6 10

5 6 7 9 10

2 4 8 9 10

1 3 7 8 9

For more information, go to https://www.ccrwest.org/cover.html

In particular the page https://www.ccrwest.org/cover/t_pages/t ... _10_2.html contains this:

C(50,10,2) = 30

Created by Colin Barker

Method of Construction: Constructed using Simulated Annealing

1 2 3 4 5 6 7 8 9 10

1 9 11 13 19 24 25 31 33 47

1 9 12 14 21 27 28 29 43 48

1 9 15 17 20 22 23 26 40 50

1 9 16 30 34 35 37 42 45 46

1 9 18 32 36 38 39 41 44 49

2 5 11 25 26 27 28 32 38 46

2 5 12 15 16 19 22 24 44 49

2 5 13 14 23 36 41 42 45 50

2 5 17 18 21 34 35 39 47 48

2 5 20 29 30 31 33 37 40 43

3 6 11 15 21 22 25 42 45 48

3 6 12 26 31 33 34 35 36 41

3 6 13 16 18 20 27 28 39 40

3 6 14 17 19 24 30 32 37 38

3 6 23 29 43 44 46 47 49 50

4 8 12 13 14 16 17 26 46 47

4 11 12 18 23 25 30 37 39 50

4 13 15 22 29 32 34 35 38 43

4 17 27 28 31 33 42 44 45 49

4 19 20 21 24 36 40 41 46 48

7 10 11 16 17 25 29 36 41 43

7 10 12 20 32 38 40 42 45 47

7 10 13 21 26 30 37 44 48 49

7 10 14 15 18 22 31 33 39 46

7 10 19 23 24 27 28 34 35 50

8 11 14 20 25 34 35 40 44 49

8 15 22 27 28 30 36 37 41 47

8 16 21 23 31 32 33 38 48 50

8 18 19 24 26 29 39 42 43 45

### Re: Combinatorics with constraint

Thank you.

I know this site almost since its inception but it is useless when it comes to my problem.

As an example :

n=50 k=9

https://www.ccrwest.org/cover/t_pages/t ... 0_9_2.html

1 2 3 16 17 18 31 37 45

1 4 5 16 19 20 36 38 44

1 6 7 16 21 22 40 42 49

1 8 9 16 23 24 32 34 47

1 10 11 16 25 26 31 43 46

Two combinations shares 3 numbers (1-16-31), the first line and the last line

So the 30 combinations (n=50 k=10) are satisfying the constraint. That is correct. I checked them. But I think that it is not the maximal number

There are many algorithms but I do not know which one is efficient.

One thing is sure. For n=10 k=5 the constraint at most 2 numbers become only 2 numbers (no zero and no one). Why? because I you create combinations sharing zero (1-2-3-4-5 and 6-7-8-9-10) you could not create more.

There is maybe many cases depending on if n is divided by k or not.

There are cases where we could derive one set from another one by induction. I have found one.

We need to partition the sets using some criterion (to define) so each one could have its general formula and its general algorithm.

I do not know how to do it for now.

When n is divided by k (example n=50 k=10) we have almost a theorem :

The maximal number of combinations sharing zero numbers noted M(0) is equal to int(n/k)

n=50 k10 M(0)=int(50/10)=5

n=42 k=10 M(0)=int(42/10)=4

What about M(1) sharing 1 number?

M(2)?

and so on?

I know this site almost since its inception but it is useless when it comes to my problem.

As an example :

n=50 k=9

https://www.ccrwest.org/cover/t_pages/t ... 0_9_2.html

1 2 3 16 17 18 31 37 45

1 4 5 16 19 20 36 38 44

1 6 7 16 21 22 40 42 49

1 8 9 16 23 24 32 34 47

1 10 11 16 25 26 31 43 46

Two combinations shares 3 numbers (1-16-31), the first line and the last line

So the 30 combinations (n=50 k=10) are satisfying the constraint. That is correct. I checked them. But I think that it is not the maximal number

There are many algorithms but I do not know which one is efficient.

One thing is sure. For n=10 k=5 the constraint at most 2 numbers become only 2 numbers (no zero and no one). Why? because I you create combinations sharing zero (1-2-3-4-5 and 6-7-8-9-10) you could not create more.

There is maybe many cases depending on if n is divided by k or not.

There are cases where we could derive one set from another one by induction. I have found one.

We need to partition the sets using some criterion (to define) so each one could have its general formula and its general algorithm.

I do not know how to do it for now.

When n is divided by k (example n=50 k=10) we have almost a theorem :

The maximal number of combinations sharing zero numbers noted M(0) is equal to int(n/k)

n=50 k10 M(0)=int(50/10)=5

n=42 k=10 M(0)=int(42/10)=4

What about M(1) sharing 1 number?

M(2)?

and so on?

### Re: Combinatorics with constraint

Here is a code solving this problem.

It works when n is < 20 but as n grows the program become very slow.

The code is not mine but I was authorized to publish and even to optimize it.

Your comments are welcome.

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include "local.hpp"

#include

#define MAX_THREADS 8

class Timer {

private:

unsigned long begTime;

std::string _s;

public:

void start(const std::string& s) {

std::cout= elapsedTime();

}

};

struct Params{

size_t k;

size_t p;

size_t n;

Params():spd(1),steps(100000),cons(5){}

size_t spd;

size_t steps;

size_t cons;

std::string toString()const{

std::stringstream oss;

oss Container;

Comb(){}

Comb(size_t n, size_t idx):_n(n), _v(n,0), _idx(idx){}

std::string stringify() const{

std::stringstream oss;

for(size_t i=0; i= max){

return false;

}

}

}

return true;

}

size_t idx()const{return _idx;}

void insert(size_t i){

_v[i] = 1;

}

protected:

Container _v;

size_t _n;

size_t _idx;

};

struct Edge{

const Comb* _c1;

const Comb* _c2;

Edge(const Comb* c1, const Comb* c2):_c1(c1), _c2(c2){}

const Comb* beg()const{return _c1;}

const Comb* end()const{return _c2;}

};

class Graph{

typedef std::vector Container;

public:

Graph(const Container* c):_m(c){}

void addEdge(const Edge& e){

_s.push_back(e);

}

void writeDimac(const std::string& fName)const{

std::ofstream out(fName.c_str());

std::stringstream oss;

Timer t;

t.start("foor loop");

for(auto it = _s.begin(); it!=_s.end(); ++it){

oss beg()->idx();

oss end()->idx() size()size(), _s.size());

for(auto it = _s.begin(); it!=_s.end(); ++it){

g->add_edge(it->beg()->idx()-1, it->end()->idx()-1);

}

return g;

}

void writeCombis(const std::string& fName)const{

std::ofstream out(fName.c_str());

std::stringstream oss;

for(auto it = _m->begin(); it!=_m->end(); ++it){

oss idx() stringify() _s;

};

Params handleInput(int argc, char* argv[]){

if(argc combinatorial(size_t k, size_t n){

std::vector v(n);

std::vector ol(C(k,n));

std::fill(v.begin() + n - k, v.end(), true);

size_t z = 0;

do {

Comb* combination = new Comb(n, z+1);

for (size_t i = 0; i insert(i);

}

}

ol[z] = combination;

z++;

} while (std::next_permutation(v.begin(), v.end()));

return ol;

}

Graph buildGraph(size_t k, const std::vector &combs){

Graph g(&combs);

Timer t;

t.start("building graph");

auto p_comb = combs[0];

std::vector candidates;

candidates.reserve(combs.size());

for(auto it2 = combs.begin()+1; it2!=combs.end(); ++it2){

if(p_comb->compatible(**it2, k)){

g.addEdge(Edge(p_comb, *it2));

candidates.push_back(*it2);

}

}

for(auto it = candidates.begin(); it!=candidates.end(); ++it){

for(auto it2 = it+1; it2!=candidates.end(); ++it2){

if((*it)->compatible(**it2, k)){

g.addEdge(Edge(*it, *it2));

}

}

}

t.stop();

return g;

}

void go(const Graph& graph, const Params &p){

graph_t *g = graph.getGraph_t();

boost::thread threads[MAX_THREADS];

DLS *dls = new DLS[MAX_THREADS];

double start = (double)clock()/CLOCKS_PER_SEC;

std::cout n, dls);

}

std::cout " " << bests.size() << std::endl;

std::cout << "Primer mejor en " << bestFirst - start << std::endl;

delete g;

}

int main(int argc, char* argv[]){

try{

const auto ¶ms = handleInput(argc, argv);

const auto &combs = combinatorial(params.p, params.n);

std::cout<<"combis : "<<combs.size()<<std::endl;

Graph g = buildGraph(params.k, combs);

std::cout<<"built"<<std::endl;

Timer t;

t.start("write combis");

g.writeCombis("./graph.txt");

t.stop();

std::cout<<"combi ready"<<std::endl;

go(g, params);

for(auto comb: combs){

delete comb;

}

}catch(const std::string &e){

std::cout<<e<<std::endl;

std::cout<<"expects ./exe k p n \n";

std::cout<<"where \n";

std::cout<<"\t k : maximum size of intersecting set of two random combination (excluded) \n";

std::cout<<"\t p : size of combination taken from elements \n";

std::cout<<"\t n : number of elements"<<std::endl;

}

return 0;

}

It works when n is < 20 but as n grows the program become very slow.

The code is not mine but I was authorized to publish and even to optimize it.

Your comments are welcome.

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include "local.hpp"

#include

#define MAX_THREADS 8

class Timer {

private:

unsigned long begTime;

std::string _s;

public:

void start(const std::string& s) {

std::cout= elapsedTime();

}

};

struct Params{

size_t k;

size_t p;

size_t n;

Params():spd(1),steps(100000),cons(5){}

size_t spd;

size_t steps;

size_t cons;

std::string toString()const{

std::stringstream oss;

oss Container;

Comb(){}

Comb(size_t n, size_t idx):_n(n), _v(n,0), _idx(idx){}

std::string stringify() const{

std::stringstream oss;

for(size_t i=0; i= max){

return false;

}

}

}

return true;

}

size_t idx()const{return _idx;}

void insert(size_t i){

_v[i] = 1;

}

protected:

Container _v;

size_t _n;

size_t _idx;

};

struct Edge{

const Comb* _c1;

const Comb* _c2;

Edge(const Comb* c1, const Comb* c2):_c1(c1), _c2(c2){}

const Comb* beg()const{return _c1;}

const Comb* end()const{return _c2;}

};

class Graph{

typedef std::vector Container;

public:

Graph(const Container* c):_m(c){}

void addEdge(const Edge& e){

_s.push_back(e);

}

void writeDimac(const std::string& fName)const{

std::ofstream out(fName.c_str());

std::stringstream oss;

Timer t;

t.start("foor loop");

for(auto it = _s.begin(); it!=_s.end(); ++it){

oss beg()->idx();

oss end()->idx() size()size(), _s.size());

for(auto it = _s.begin(); it!=_s.end(); ++it){

g->add_edge(it->beg()->idx()-1, it->end()->idx()-1);

}

return g;

}

void writeCombis(const std::string& fName)const{

std::ofstream out(fName.c_str());

std::stringstream oss;

for(auto it = _m->begin(); it!=_m->end(); ++it){

oss idx() stringify() _s;

};

Params handleInput(int argc, char* argv[]){

if(argc combinatorial(size_t k, size_t n){

std::vector v(n);

std::vector ol(C(k,n));

std::fill(v.begin() + n - k, v.end(), true);

size_t z = 0;

do {

Comb* combination = new Comb(n, z+1);

for (size_t i = 0; i insert(i);

}

}

ol[z] = combination;

z++;

} while (std::next_permutation(v.begin(), v.end()));

return ol;

}

Graph buildGraph(size_t k, const std::vector &combs){

Graph g(&combs);

Timer t;

t.start("building graph");

auto p_comb = combs[0];

std::vector candidates;

candidates.reserve(combs.size());

for(auto it2 = combs.begin()+1; it2!=combs.end(); ++it2){

if(p_comb->compatible(**it2, k)){

g.addEdge(Edge(p_comb, *it2));

candidates.push_back(*it2);

}

}

for(auto it = candidates.begin(); it!=candidates.end(); ++it){

for(auto it2 = it+1; it2!=candidates.end(); ++it2){

if((*it)->compatible(**it2, k)){

g.addEdge(Edge(*it, *it2));

}

}

}

t.stop();

return g;

}

void go(const Graph& graph, const Params &p){

graph_t *g = graph.getGraph_t();

boost::thread threads[MAX_THREADS];

DLS *dls = new DLS[MAX_THREADS];

double start = (double)clock()/CLOCKS_PER_SEC;

std::cout n, dls);

}

std::cout " " << bests.size() << std::endl;

std::cout << "Primer mejor en " << bestFirst - start << std::endl;

delete g;

}

int main(int argc, char* argv[]){

try{

const auto ¶ms = handleInput(argc, argv);

const auto &combs = combinatorial(params.p, params.n);

std::cout<<"combis : "<<combs.size()<<std::endl;

Graph g = buildGraph(params.k, combs);

std::cout<<"built"<<std::endl;

Timer t;

t.start("write combis");

g.writeCombis("./graph.txt");

t.stop();

std::cout<<"combi ready"<<std::endl;

go(g, params);

for(auto comb: combs){

delete comb;

}

}catch(const std::string &e){

std::cout<<e<<std::endl;

std::cout<<"expects ./exe k p n \n";

std::cout<<"where \n";

std::cout<<"\t k : maximum size of intersecting set of two random combination (excluded) \n";

std::cout<<"\t p : size of combination taken from elements \n";

std::cout<<"\t n : number of elements"<<std::endl;

}

return 0;

}

### Re: Combinatorics with constraint

There are a lot of things syntactically wrong with that code.

Edit: I think anything between <angle> brackets may have been filtered out. That would account for the blank #includes and some missing template parameters.

Edit: I think anything between <angle> brackets may have been filtered out. That would account for the blank #includes and some missing template parameters.

gmalivuk wrote:Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.

### Re: Combinatorics with constraint

Sizik wrote:There are a lot of things syntactically wrong with that code.

Edit: I think anything between <angle> brackets may have been filtered out. That would account for the blank #includes and some missing template parameters.

I have no idea about coding but here in this thread you will find all the codes :

https://www.maths-forum.com/enigmes/com ... 62-80.html

It is in french but all the codes are in gray so you could easily copy-paste them

The guy told me that he used algorithm maximum clique. He found it in some url and adapted it to my problem.

### Who is online

Users browsing this forum: No registered users and 11 guests