Combinatorics with constraint

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Combinatorics with constraint

Postby Goahead52 » Sat Jan 21, 2017 11:47 am UTC

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

DavidSh
Posts: 64
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: Combinatorics with constraint

Postby DavidSh » Sat Jan 21, 2017 3:30 pm UTC

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:

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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Combinatorics with constraint

Postby Goahead52 » Tue Jan 24, 2017 4:41 pm UTC

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?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Combinatorics with constraint

Postby Goahead52 » Wed Jan 25, 2017 12:30 pm UTC

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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Combinatorics with constraint

Postby Goahead52 » Wed Jan 25, 2017 5:40 pm UTC

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?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Combinatorics with constraint

Postby Goahead52 » Wed Jan 25, 2017 9:42 pm UTC

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.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25740
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Combinatorics with constraint

Postby gmalivuk » Wed Jan 25, 2017 10:34 pm UTC

Dude, you can edit posts to add additional information. Please don't post 3 or 4 times in a row.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

DavidSh
Posts: 64
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: Combinatorics with constraint

Postby DavidSh » Thu Jan 26, 2017 2:24 am UTC

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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Combinatorics with constraint

Postby Goahead52 » Thu Jan 26, 2017 3:37 pm UTC

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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Combinatorics with constraint

Postby Goahead52 » Fri Jan 27, 2017 5:18 pm UTC

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).

gribgrub
Posts: 4
Joined: Sun Dec 13, 2009 10:34 pm UTC

Re: Combinatorics with constraint

Postby gribgrub » Tue Jan 31, 2017 2:58 am UTC

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

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Combinatorics with constraint

Postby Goahead52 » Tue Jan 31, 2017 11:17 am UTC

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?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Combinatorics with constraint

Postby Goahead52 » Fri Feb 03, 2017 1:05 pm UTC

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 &params = 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;
}

User avatar
Sizik
Posts: 1144
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Combinatorics with constraint

Postby Sizik » Fri Feb 03, 2017 3:18 pm UTC

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.
gmalivuk wrote:
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.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Combinatorics with constraint

Postby Goahead52 » Fri Feb 03, 2017 3:43 pm UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 7 guests