Finding an algorithm for all combinations [closed]
$begingroup$
I need an answer on a question Im confronted writing a program. So I recently askend on Stackoverflow but I hope to get some better results from the mathematics site.
I need to go through an array of objects with n entries. I need to check almost every combination. Lets say the lists contains $lbrace 0,1,2,3 rbrace$ (Im matching the objects values to their index here for explenation). We fix the first one. This is the start value for all combinations. From 0 we choose one of the three objects left. This gives $n! = 4!$ combinations but we consider the combinations $0 - 1 - 2 - 3$ and $0 - 3 - 2 - 1$ to be the same because their last $(n-1)$ digits are the same in reverse order. With that the combination $0 - 2 - 1 - 3$ and $0 - 3 - 1 - 2$ give the same result and I dont have to look at both of them.
Do you know an effective way of getting an algorithm which gives me the $j$-th combination for j out of $1,...,dfrac{(n-1)!}{2}$ ?
It seems to be pretty similiar to the travelling salesman problem where you have a starting point $0$ and have to visit all the other places. This way you might understand a little bit better how $0 - 1 - 2 - 3$ and $0 - 3 - 2 - 1$ are giving the same result. Its just like going around the other way.
combinatorics graph-theory combinations
asked Dec 25 '18 at 22:29
ArjihadArjihad
390112
$endgroup$
closed as off-topic by Namaste, Don Thousand, KReiser, Eevee Trainer, Lord_Farin Dec 26 '18 at 9:32
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is not about mathematics, within the scope defined in the help center." – Namaste, Don Thousand, KReiser, Eevee Trainer, Lord_Farin
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
I need an answer on a question Im confronted writing a program. So I recently askend on Stackoverflow but I hope to get some better results from the mathematics site.
I need to go through an array of objects with n entries. I need to check almost every combination. Lets say the lists contains $lbrace 0,1,2,3 rbrace$ (Im matching the objects values to their index here for explenation). We fix the first one. This is the start value for all combinations. From 0 we choose one of the three objects left. This gives $n! = 4!$ combinations but we consider the combinations $0 - 1 - 2 - 3$ and $0 - 3 - 2 - 1$ to be the same because their last $(n-1)$ digits are the same in reverse order. With that the combination $0 - 2 - 1 - 3$ and $0 - 3 - 1 - 2$ give the same result and I dont have to look at both of them.
Do you know an effective way of getting an algorithm which gives me the $j$-th combination for j out of $1,...,dfrac{(n-1)!}{2}$ ?
It seems to be pretty similiar to the travelling salesman problem where you have a starting point $0$ and have to visit all the other places. This way you might understand a little bit better how $0 - 1 - 2 - 3$ and $0 - 3 - 2 - 1$ are giving the same result. Its just like going around the other way.
combinatorics graph-theory combinations
asked Dec 25 '18 at 22:29
ArjihadArjihad
390112
$endgroup$
closed as off-topic by Namaste, Don Thousand, KReiser, Eevee Trainer, Lord_Farin Dec 26 '18 at 9:32
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is not about mathematics, within the scope defined in the help center." – Namaste, Don Thousand, KReiser, Eevee Trainer, Lord_Farin
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
It might help to link to your SO Question and explain what lack there is in the Answers provided there. Selecting a "combination" means not only from a set of size $n$ but also specifying the size $k$ of a subset to be selected.
$endgroup$
– hardmath
Dec 25 '18 at 22:56
add a comment |
$begingroup$
I need an answer on a question Im confronted writing a program. So I recently askend on Stackoverflow but I hope to get some better results from the mathematics site.
I need to go through an array of objects with n entries. I need to check almost every combination. Lets say the lists contains $lbrace 0,1,2,3 rbrace$ (Im matching the objects values to their index here for explenation). We fix the first one. This is the start value for all combinations. From 0 we choose one of the three objects left. This gives $n! = 4!$ combinations but we consider the combinations $0 - 1 - 2 - 3$ and $0 - 3 - 2 - 1$ to be the same because their last $(n-1)$ digits are the same in reverse order. With that the combination $0 - 2 - 1 - 3$ and $0 - 3 - 1 - 2$ give the same result and I dont have to look at both of them.
Do you know an effective way of getting an algorithm which gives me the $j$-th combination for j out of $1,...,dfrac{(n-1)!}{2}$ ?
It seems to be pretty similiar to the travelling salesman problem where you have a starting point $0$ and have to visit all the other places. This way you might understand a little bit better how $0 - 1 - 2 - 3$ and $0 - 3 - 2 - 1$ are giving the same result. Its just like going around the other way.
combinatorics graph-theory combinations
asked Dec 25 '18 at 22:29
ArjihadArjihad
390112
$endgroup$
I need an answer on a question Im confronted writing a program. So I recently askend on Stackoverflow but I hope to get some better results from the mathematics site.
I need to go through an array of objects with n entries. I need to check almost every combination. Lets say the lists contains $lbrace 0,1,2,3 rbrace$ (Im matching the objects values to their index here for explenation). We fix the first one. This is the start value for all combinations. From 0 we choose one of the three objects left. This gives $n! = 4!$ combinations but we consider the combinations $0 - 1 - 2 - 3$ and $0 - 3 - 2 - 1$ to be the same because their last $(n-1)$ digits are the same in reverse order. With that the combination $0 - 2 - 1 - 3$ and $0 - 3 - 1 - 2$ give the same result and I dont have to look at both of them.
Do you know an effective way of getting an algorithm which gives me the $j$-th combination for j out of $1,...,dfrac{(n-1)!}{2}$ ?
It seems to be pretty similiar to the travelling salesman problem where you have a starting point $0$ and have to visit all the other places. This way you might understand a little bit better how $0 - 1 - 2 - 3$ and $0 - 3 - 2 - 1$ are giving the same result. Its just like going around the other way.
combinatorics graph-theory combinations
combinatorics graph-theory combinations
asked Dec 25 '18 at 22:29
ArjihadArjihad
390112
asked Dec 25 '18 at 22:29
ArjihadArjihad
390112
asked Dec 25 '18 at 22:29
ArjihadArjihad
390112
asked Dec 25 '18 at 22:29
ArjihadArjihad
390112
asked Dec 25 '18 at 22:29
ArjihadArjihad
390112
390112
closed as off-topic by Namaste, Don Thousand, KReiser, Eevee Trainer, Lord_Farin Dec 26 '18 at 9:32
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is not about mathematics, within the scope defined in the help center." – Namaste, Don Thousand, KReiser, Eevee Trainer, Lord_Farin
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Namaste, Don Thousand, KReiser, Eevee Trainer, Lord_Farin Dec 26 '18 at 9:32
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is not about mathematics, within the scope defined in the help center." – Namaste, Don Thousand, KReiser, Eevee Trainer, Lord_Farin
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
It might help to link to your SO Question and explain what lack there is in the Answers provided there. Selecting a "combination" means not only from a set of size $n$ but also specifying the size $k$ of a subset to be selected.
$endgroup$
– hardmath
Dec 25 '18 at 22:56
add a comment |
$begingroup$
It might help to link to your SO Question and explain what lack there is in the Answers provided there. Selecting a "combination" means not only from a set of size $n$ but also specifying the size $k$ of a subset to be selected.
$endgroup$
– hardmath
Dec 25 '18 at 22:56
$begingroup$
It might help to link to your SO Question and explain what lack there is in the Answers provided there. Selecting a "combination" means not only from a set of size $n$ but also specifying the size $k$ of a subset to be selected.
$endgroup$
– hardmath
Dec 25 '18 at 22:56
$begingroup$
It might help to link to your SO Question and explain what lack there is in the Answers provided there. Selecting a "combination" means not only from a set of size $n$ but also specifying the size $k$ of a subset to be selected.
$endgroup$
– hardmath
Dec 25 '18 at 22:56
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
I am interpreting your question to indicate that you want a math algorithm that you can code into a computer program. I would do this as follows:
1. construing the element-0 as home base, you have (n-1) choices for the element-1. Once element-1 has been chosen, you then have (n-2) choices for element-2. Continuing, you will generate (n-1)! candidate sequences.
2. every time that you generate a candidate sequence you check whether the reverse of that sequence has already been added to your list of sequences. If so, discard the candidate sequence. If not, add the candidate sequence to your list of sequences.
This will result in your list having (n-1)!/2 rather than (n-1)! sequences.
Please provide comment if I have misunderstood your question.
answered Dec 25 '18 at 22:50
user2661923user2661923
556112
$endgroup$
add a comment |
$begingroup$
If I understand your question correctly, it seems you want to generate all Hamiltonian cycles in a complete undirected graph with $n$ vertices. The number of different cycles is, as you say, $frac{(n-1)!}{2}$.
An efficient way to do this is described in the answer here.
First, find an algorithm which generates permutations sequentially. An example is algorithm $2$ here.
Second, starting with the list ${2,3,ldots , n }$ (the first element $1$ is fixed) generate permutations of this list. If the first element of that permutation is larger than the last element, discard it, otherwise keep it.
And you're done.
This algorithm will check less than $(n-1)!$ permutations.
answered Dec 26 '18 at 3:26
JensJens
4,03721032
$endgroup$
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I am interpreting your question to indicate that you want a math algorithm that you can code into a computer program. I would do this as follows:
1. construing the element-0 as home base, you have (n-1) choices for the element-1. Once element-1 has been chosen, you then have (n-2) choices for element-2. Continuing, you will generate (n-1)! candidate sequences.
2. every time that you generate a candidate sequence you check whether the reverse of that sequence has already been added to your list of sequences. If so, discard the candidate sequence. If not, add the candidate sequence to your list of sequences.
This will result in your list having (n-1)!/2 rather than (n-1)! sequences.
Please provide comment if I have misunderstood your question.
answered Dec 25 '18 at 22:50
user2661923user2661923
556112
$endgroup$
add a comment |
$begingroup$
I am interpreting your question to indicate that you want a math algorithm that you can code into a computer program. I would do this as follows:
1. construing the element-0 as home base, you have (n-1) choices for the element-1. Once element-1 has been chosen, you then have (n-2) choices for element-2. Continuing, you will generate (n-1)! candidate sequences.
2. every time that you generate a candidate sequence you check whether the reverse of that sequence has already been added to your list of sequences. If so, discard the candidate sequence. If not, add the candidate sequence to your list of sequences.
This will result in your list having (n-1)!/2 rather than (n-1)! sequences.
Please provide comment if I have misunderstood your question.
answered Dec 25 '18 at 22:50
user2661923user2661923
556112
$endgroup$
add a comment |
$begingroup$
I am interpreting your question to indicate that you want a math algorithm that you can code into a computer program. I would do this as follows:
1. construing the element-0 as home base, you have (n-1) choices for the element-1. Once element-1 has been chosen, you then have (n-2) choices for element-2. Continuing, you will generate (n-1)! candidate sequences.
2. every time that you generate a candidate sequence you check whether the reverse of that sequence has already been added to your list of sequences. If so, discard the candidate sequence. If not, add the candidate sequence to your list of sequences.
This will result in your list having (n-1)!/2 rather than (n-1)! sequences.
Please provide comment if I have misunderstood your question.
answered Dec 25 '18 at 22:50
user2661923user2661923
556112
$endgroup$
I am interpreting your question to indicate that you want a math algorithm that you can code into a computer program. I would do this as follows:
1. construing the element-0 as home base, you have (n-1) choices for the element-1. Once element-1 has been chosen, you then have (n-2) choices for element-2. Continuing, you will generate (n-1)! candidate sequences.
2. every time that you generate a candidate sequence you check whether the reverse of that sequence has already been added to your list of sequences. If so, discard the candidate sequence. If not, add the candidate sequence to your list of sequences.
This will result in your list having (n-1)!/2 rather than (n-1)! sequences.
Please provide comment if I have misunderstood your question.
answered Dec 25 '18 at 22:50
user2661923user2661923
556112
answered Dec 25 '18 at 22:50
user2661923user2661923
556112
answered Dec 25 '18 at 22:50
user2661923user2661923
556112
answered Dec 25 '18 at 22:50
user2661923user2661923
556112
556112
add a comment |
add a comment |
$begingroup$
If I understand your question correctly, it seems you want to generate all Hamiltonian cycles in a complete undirected graph with $n$ vertices. The number of different cycles is, as you say, $frac{(n-1)!}{2}$.
An efficient way to do this is described in the answer here.
First, find an algorithm which generates permutations sequentially. An example is algorithm $2$ here.
Second, starting with the list ${2,3,ldots , n }$ (the first element $1$ is fixed) generate permutations of this list. If the first element of that permutation is larger than the last element, discard it, otherwise keep it.
And you're done.
This algorithm will check less than $(n-1)!$ permutations.
answered Dec 26 '18 at 3:26
JensJens
4,03721032
$endgroup$
add a comment |
$begingroup$
If I understand your question correctly, it seems you want to generate all Hamiltonian cycles in a complete undirected graph with $n$ vertices. The number of different cycles is, as you say, $frac{(n-1)!}{2}$.
An efficient way to do this is described in the answer here.
First, find an algorithm which generates permutations sequentially. An example is algorithm $2$ here.
Second, starting with the list ${2,3,ldots , n }$ (the first element $1$ is fixed) generate permutations of this list. If the first element of that permutation is larger than the last element, discard it, otherwise keep it.
And you're done.
This algorithm will check less than $(n-1)!$ permutations.
answered Dec 26 '18 at 3:26
JensJens
4,03721032
$endgroup$
add a comment |
$begingroup$
If I understand your question correctly, it seems you want to generate all Hamiltonian cycles in a complete undirected graph with $n$ vertices. The number of different cycles is, as you say, $frac{(n-1)!}{2}$.
An efficient way to do this is described in the answer here.
First, find an algorithm which generates permutations sequentially. An example is algorithm $2$ here.
Second, starting with the list ${2,3,ldots , n }$ (the first element $1$ is fixed) generate permutations of this list. If the first element of that permutation is larger than the last element, discard it, otherwise keep it.
And you're done.
This algorithm will check less than $(n-1)!$ permutations.
answered Dec 26 '18 at 3:26
JensJens
4,03721032
$endgroup$
If I understand your question correctly, it seems you want to generate all Hamiltonian cycles in a complete undirected graph with $n$ vertices. The number of different cycles is, as you say, $frac{(n-1)!}{2}$.
An efficient way to do this is described in the answer here.
First, find an algorithm which generates permutations sequentially. An example is algorithm $2$ here.
Second, starting with the list ${2,3,ldots , n }$ (the first element $1$ is fixed) generate permutations of this list. If the first element of that permutation is larger than the last element, discard it, otherwise keep it.
And you're done.
This algorithm will check less than $(n-1)!$ permutations.
answered Dec 26 '18 at 3:26
JensJens
4,03721032
answered Dec 26 '18 at 3:26
JensJens
4,03721032
answered Dec 26 '18 at 3:26
JensJens
4,03721032
answered Dec 26 '18 at 3:26
JensJens
4,03721032
4,03721032
add a comment |
add a comment |
$begingroup$
It might help to link to your SO Question and explain what lack there is in the Answers provided there. Selecting a "combination" means not only from a set of size $n$ but also specifying the size $k$ of a subset to be selected.
$endgroup$
– hardmath
Dec 25 '18 at 22:56