Mixing
enumerating permutations, relative to each “memberâ€
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
As always, I need to put a disclaimer that I apologize for any misuse of terminology. My education is a bit lacking. Please note this is super long, the TLDR at the bottom may be sufficient. Also it's possible I made mistakes. Hopefully not.
Setting up the problem
Anyways, I am enumerating permutations of.. anything, using a matrix and iterations.
Let's call what I am enumerating permutations of "nodes". If I have n nodes, I use a Z*N matrix, where Z is the number of iterations I want to do.
I begin by placing a 1 in every pertinent column of the first row of my matrix. I then, for each iteration level i and column j, add matrix[(i,j)] to matrix[((i+1),(0...n)]
So, at this point, I want to add some constraints to my enumeration. The particular constraints don't matter, but I do need to track how many permutations came from where, in order to see if I am within constraints.
Therefore, for each current iteration row, I keep a "tracking array" of size N for each node. Within this array, I keep a count of how many permutations passed through each node to get here.
Example, 5x5 matrix, enumerating from node 2. Let's throw in the rule that a node can't pass back to itself in the next row, just to make it more interesting:
0,0,1,0,0
1,1,0,1,1
3,3,4,3,3
...
...
at this point, we have an array for nodes 0,1,2,3,4 of row 2. if we looked at the array for node 0, it would show:
[3,1,3,1,1]
this is because for row2, node 0, it currently has 3 of node 0 at it, and 3 of node 2 at it (all 3 permutations ending in row 2, node 0 began at row 0, node 2). the rest are all 1 which is easy to understand.
Using this information we could perform reductions to our counting based on various constraints, such as putting limits on the number of nodes in a given row, or limiting what node can go to others, or how often nodes can go to others, etc etc.
The actual problem
But there is a part of this I can't figure out.. and I am not sure if it's even possible (maybe it's NP complete?). That problem is "reconstructing" the tracking array after reductions are done due to constraints.
for example, look back at our matrix
0,0,1,0,0
1,1,0,1,1
3,3,4,3,3
...
...
Let's say we have a constraint. At row 3, we will not accept any permutations that use node 4. Now let's try to solve for node 0, row 3.
The pertinent incoming nodes from row 2 are node 1, node 2, and node 3 (we cannot accept from node 0 or node 4).
The incoming count would be 3+3+4, but we must reduce this because some of these permutations use node 4.
We look at the tracking arrays of node1, 2, and 3
1: [1,3,3,1,1]
2: [1,1,4,1,1]
3: [1,1,3,3,1]
So for each incoming count, we actually need to subtract one, because each node has a permutation that passed through 4.
And now, the specific problem:
I need to construct my "tracking array" for row 3, node 0. When there are no constraints, I can simply sum the previous tracking arrays to construct the new one. But in this case, there were applicable constraints and I can't do that.
This matrix is small and easy enough I could do it just by looking at it.
1: [1,3,3,1,1]
2: [1,1,4,1,1]
3: [1,1,3,3,1]
remove the node 4s:
1: [1,2,2,1,0]
2: [1,1,3,1,0]
3: [1,1,2,2,0]
now sum:
[3,4,7,4,0]
but, when there are many more rows, where other constraints have previously been met... it gets to the point where I can't seem to reconstruct it. If, for example, I had the constraint of "I can't accept permutations with node 4", then I need to know not only how many times 4 is in the permutations that got to each node - but I also need to know how many times 4 is in the permutations that node 1 got to node 2, and how many times 4 is in the permutations that node 1 got to node 2 that got to node 3 - etc etc. So is this even possible to do?
ATTEMPT AT A TLDR
When enumerating permutations of items, is it possible to, at any given stage in enumeration:
1.) track how many permutations, ending in item 0...N, went through each other item 0...N
AND
2.) remove counts of permutations based on this information
AND
3.) modify the tracking information accurately based on 2.
Thank you
combinatorics matrices discrete-mathematics permutations
edited Jul 21 at 22:40
Alexander Konovalov
4,81721856
asked Jul 20 at 17:10
Travis Black
15619
add a comment |Â
up vote
1
down vote
favorite
As always, I need to put a disclaimer that I apologize for any misuse of terminology. My education is a bit lacking. Please note this is super long, the TLDR at the bottom may be sufficient. Also it's possible I made mistakes. Hopefully not.
Setting up the problem
Anyways, I am enumerating permutations of.. anything, using a matrix and iterations.
Let's call what I am enumerating permutations of "nodes". If I have n nodes, I use a Z*N matrix, where Z is the number of iterations I want to do.
I begin by placing a 1 in every pertinent column of the first row of my matrix. I then, for each iteration level i and column j, add matrix[(i,j)] to matrix[((i+1),(0...n)]
So, at this point, I want to add some constraints to my enumeration. The particular constraints don't matter, but I do need to track how many permutations came from where, in order to see if I am within constraints.
Therefore, for each current iteration row, I keep a "tracking array" of size N for each node. Within this array, I keep a count of how many permutations passed through each node to get here.
Example, 5x5 matrix, enumerating from node 2. Let's throw in the rule that a node can't pass back to itself in the next row, just to make it more interesting:
0,0,1,0,0
1,1,0,1,1
3,3,4,3,3
...
...
at this point, we have an array for nodes 0,1,2,3,4 of row 2. if we looked at the array for node 0, it would show:
[3,1,3,1,1]
this is because for row2, node 0, it currently has 3 of node 0 at it, and 3 of node 2 at it (all 3 permutations ending in row 2, node 0 began at row 0, node 2). the rest are all 1 which is easy to understand.
Using this information we could perform reductions to our counting based on various constraints, such as putting limits on the number of nodes in a given row, or limiting what node can go to others, or how often nodes can go to others, etc etc.
The actual problem
But there is a part of this I can't figure out.. and I am not sure if it's even possible (maybe it's NP complete?). That problem is "reconstructing" the tracking array after reductions are done due to constraints.
for example, look back at our matrix
0,0,1,0,0
1,1,0,1,1
3,3,4,3,3
...
...
Let's say we have a constraint. At row 3, we will not accept any permutations that use node 4. Now let's try to solve for node 0, row 3.
The pertinent incoming nodes from row 2 are node 1, node 2, and node 3 (we cannot accept from node 0 or node 4).
The incoming count would be 3+3+4, but we must reduce this because some of these permutations use node 4.
We look at the tracking arrays of node1, 2, and 3
1: [1,3,3,1,1]
2: [1,1,4,1,1]
3: [1,1,3,3,1]
So for each incoming count, we actually need to subtract one, because each node has a permutation that passed through 4.
And now, the specific problem:
I need to construct my "tracking array" for row 3, node 0. When there are no constraints, I can simply sum the previous tracking arrays to construct the new one. But in this case, there were applicable constraints and I can't do that.
This matrix is small and easy enough I could do it just by looking at it.
1: [1,3,3,1,1]
2: [1,1,4,1,1]
3: [1,1,3,3,1]
remove the node 4s:
1: [1,2,2,1,0]
2: [1,1,3,1,0]
3: [1,1,2,2,0]
now sum:
[3,4,7,4,0]
but, when there are many more rows, where other constraints have previously been met... it gets to the point where I can't seem to reconstruct it. If, for example, I had the constraint of "I can't accept permutations with node 4", then I need to know not only how many times 4 is in the permutations that got to each node - but I also need to know how many times 4 is in the permutations that node 1 got to node 2, and how many times 4 is in the permutations that node 1 got to node 2 that got to node 3 - etc etc. So is this even possible to do?
ATTEMPT AT A TLDR
When enumerating permutations of items, is it possible to, at any given stage in enumeration:
1.) track how many permutations, ending in item 0...N, went through each other item 0...N
AND
2.) remove counts of permutations based on this information
AND
3.) modify the tracking information accurately based on 2.
Thank you
combinatorics matrices discrete-mathematics permutations
edited Jul 21 at 22:40
Alexander Konovalov
4,81721856
asked Jul 20 at 17:10
Travis Black
15619
It's hard to follow your explanations, because you talk about permutations but then throw in constraints, etc. If I understand (1.) correctly, that's defined as the number of inversions.
– Alex R.
Jul 21 at 23:57
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
As always, I need to put a disclaimer that I apologize for any misuse of terminology. My education is a bit lacking. Please note this is super long, the TLDR at the bottom may be sufficient. Also it's possible I made mistakes. Hopefully not.
Setting up the problem
Anyways, I am enumerating permutations of.. anything, using a matrix and iterations.
Let's call what I am enumerating permutations of "nodes". If I have n nodes, I use a Z*N matrix, where Z is the number of iterations I want to do.
I begin by placing a 1 in every pertinent column of the first row of my matrix. I then, for each iteration level i and column j, add matrix[(i,j)] to matrix[((i+1),(0...n)]
So, at this point, I want to add some constraints to my enumeration. The particular constraints don't matter, but I do need to track how many permutations came from where, in order to see if I am within constraints.
Therefore, for each current iteration row, I keep a "tracking array" of size N for each node. Within this array, I keep a count of how many permutations passed through each node to get here.
Example, 5x5 matrix, enumerating from node 2. Let's throw in the rule that a node can't pass back to itself in the next row, just to make it more interesting:
0,0,1,0,0
1,1,0,1,1
3,3,4,3,3
...
...
at this point, we have an array for nodes 0,1,2,3,4 of row 2. if we looked at the array for node 0, it would show:
[3,1,3,1,1]
this is because for row2, node 0, it currently has 3 of node 0 at it, and 3 of node 2 at it (all 3 permutations ending in row 2, node 0 began at row 0, node 2). the rest are all 1 which is easy to understand.
Using this information we could perform reductions to our counting based on various constraints, such as putting limits on the number of nodes in a given row, or limiting what node can go to others, or how often nodes can go to others, etc etc.
The actual problem
But there is a part of this I can't figure out.. and I am not sure if it's even possible (maybe it's NP complete?). That problem is "reconstructing" the tracking array after reductions are done due to constraints.
for example, look back at our matrix
0,0,1,0,0
1,1,0,1,1
3,3,4,3,3
...
...
Let's say we have a constraint. At row 3, we will not accept any permutations that use node 4. Now let's try to solve for node 0, row 3.
The pertinent incoming nodes from row 2 are node 1, node 2, and node 3 (we cannot accept from node 0 or node 4).
The incoming count would be 3+3+4, but we must reduce this because some of these permutations use node 4.
We look at the tracking arrays of node1, 2, and 3
1: [1,3,3,1,1]
2: [1,1,4,1,1]
3: [1,1,3,3,1]
So for each incoming count, we actually need to subtract one, because each node has a permutation that passed through 4.
And now, the specific problem:
I need to construct my "tracking array" for row 3, node 0. When there are no constraints, I can simply sum the previous tracking arrays to construct the new one. But in this case, there were applicable constraints and I can't do that.
This matrix is small and easy enough I could do it just by looking at it.
1: [1,3,3,1,1]
2: [1,1,4,1,1]
3: [1,1,3,3,1]
remove the node 4s:
1: [1,2,2,1,0]
2: [1,1,3,1,0]
3: [1,1,2,2,0]
now sum:
[3,4,7,4,0]
but, when there are many more rows, where other constraints have previously been met... it gets to the point where I can't seem to reconstruct it. If, for example, I had the constraint of "I can't accept permutations with node 4", then I need to know not only how many times 4 is in the permutations that got to each node - but I also need to know how many times 4 is in the permutations that node 1 got to node 2, and how many times 4 is in the permutations that node 1 got to node 2 that got to node 3 - etc etc. So is this even possible to do?
ATTEMPT AT A TLDR
When enumerating permutations of items, is it possible to, at any given stage in enumeration:
1.) track how many permutations, ending in item 0...N, went through each other item 0...N
AND
2.) remove counts of permutations based on this information
AND
3.) modify the tracking information accurately based on 2.
Thank you
combinatorics matrices discrete-mathematics permutations
edited Jul 21 at 22:40
Alexander Konovalov
4,81721856
asked Jul 20 at 17:10
Travis Black
15619
As always, I need to put a disclaimer that I apologize for any misuse of terminology. My education is a bit lacking. Please note this is super long, the TLDR at the bottom may be sufficient. Also it's possible I made mistakes. Hopefully not.
Setting up the problem
Anyways, I am enumerating permutations of.. anything, using a matrix and iterations.
Let's call what I am enumerating permutations of "nodes". If I have n nodes, I use a Z*N matrix, where Z is the number of iterations I want to do.
I begin by placing a 1 in every pertinent column of the first row of my matrix. I then, for each iteration level i and column j, add matrix[(i,j)] to matrix[((i+1),(0...n)]
So, at this point, I want to add some constraints to my enumeration. The particular constraints don't matter, but I do need to track how many permutations came from where, in order to see if I am within constraints.
Therefore, for each current iteration row, I keep a "tracking array" of size N for each node. Within this array, I keep a count of how many permutations passed through each node to get here.
Example, 5x5 matrix, enumerating from node 2. Let's throw in the rule that a node can't pass back to itself in the next row, just to make it more interesting:
0,0,1,0,0
1,1,0,1,1
3,3,4,3,3
...
...
at this point, we have an array for nodes 0,1,2,3,4 of row 2. if we looked at the array for node 0, it would show:
[3,1,3,1,1]
this is because for row2, node 0, it currently has 3 of node 0 at it, and 3 of node 2 at it (all 3 permutations ending in row 2, node 0 began at row 0, node 2). the rest are all 1 which is easy to understand.
Using this information we could perform reductions to our counting based on various constraints, such as putting limits on the number of nodes in a given row, or limiting what node can go to others, or how often nodes can go to others, etc etc.
The actual problem
But there is a part of this I can't figure out.. and I am not sure if it's even possible (maybe it's NP complete?). That problem is "reconstructing" the tracking array after reductions are done due to constraints.
for example, look back at our matrix
0,0,1,0,0
1,1,0,1,1
3,3,4,3,3
...
...
Let's say we have a constraint. At row 3, we will not accept any permutations that use node 4. Now let's try to solve for node 0, row 3.
The pertinent incoming nodes from row 2 are node 1, node 2, and node 3 (we cannot accept from node 0 or node 4).
The incoming count would be 3+3+4, but we must reduce this because some of these permutations use node 4.
We look at the tracking arrays of node1, 2, and 3
1: [1,3,3,1,1]
2: [1,1,4,1,1]
3: [1,1,3,3,1]
So for each incoming count, we actually need to subtract one, because each node has a permutation that passed through 4.
And now, the specific problem:
I need to construct my "tracking array" for row 3, node 0. When there are no constraints, I can simply sum the previous tracking arrays to construct the new one. But in this case, there were applicable constraints and I can't do that.
This matrix is small and easy enough I could do it just by looking at it.
1: [1,3,3,1,1]
2: [1,1,4,1,1]
3: [1,1,3,3,1]
remove the node 4s:
1: [1,2,2,1,0]
2: [1,1,3,1,0]
3: [1,1,2,2,0]
now sum:
[3,4,7,4,0]
but, when there are many more rows, where other constraints have previously been met... it gets to the point where I can't seem to reconstruct it. If, for example, I had the constraint of "I can't accept permutations with node 4", then I need to know not only how many times 4 is in the permutations that got to each node - but I also need to know how many times 4 is in the permutations that node 1 got to node 2, and how many times 4 is in the permutations that node 1 got to node 2 that got to node 3 - etc etc. So is this even possible to do?
ATTEMPT AT A TLDR
When enumerating permutations of items, is it possible to, at any given stage in enumeration:
1.) track how many permutations, ending in item 0...N, went through each other item 0...N
AND
2.) remove counts of permutations based on this information
AND
3.) modify the tracking information accurately based on 2.
Thank you
combinatorics matrices discrete-mathematics permutations
edited Jul 21 at 22:40
Alexander Konovalov
4,81721856
asked Jul 20 at 17:10
Travis Black
15619
edited Jul 21 at 22:40
Alexander Konovalov
4,81721856
edited Jul 21 at 22:40
Alexander Konovalov
4,81721856
edited Jul 21 at 22:40
Alexander Konovalov
4,81721856
4,81721856
asked Jul 20 at 17:10
Travis Black
15619
asked Jul 20 at 17:10
Travis Black
15619
asked Jul 20 at 17:10
Travis Black
15619
15619
It's hard to follow your explanations, because you talk about permutations but then throw in constraints, etc. If I understand (1.) correctly, that's defined as the number of inversions.
– Alex R.
Jul 21 at 23:57
add a comment |Â
It's hard to follow your explanations, because you talk about permutations but then throw in constraints, etc. If I understand (1.) correctly, that's defined as the number of inversions.
– Alex R.
Jul 21 at 23:57
It's hard to follow your explanations, because you talk about permutations but then throw in constraints, etc. If I understand (1.) correctly, that's defined as the number of inversions.
– Alex R.
Jul 21 at 23:57
It's hard to follow your explanations, because you talk about permutations but then throw in constraints, etc. If I understand (1.) correctly, that's defined as the number of inversions.
– Alex R.
Jul 21 at 23:57
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2857846%2fenumerating-permutations-relative-to-each-member%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
It's hard to follow your explanations, because you talk about permutations but then throw in constraints, etc. If I understand (1.) correctly, that's defined as the number of inversions.
– Alex R.
Jul 21 at 23:57