Count permutation of an Array
Suppose we have an array of length z. Which consists of x different even numbers and y different odd numbers.
So z = x+y.
We also know that x => 1 always applies.
1st question: How many different arrays of length z there are. That should be exactly z! many or?
2nd question: How many different arrays are there so that the last even number in the array is on an odd index. (The array in this example starts with index 1)
Examples:
1) [1,2,3,4,5] This array has length 5. The last even number in the array is 4 and has index 4 in the array, so we don't count such an array.
2) [52,3,14]. The last even number in this array is 14 and has index 3. So such an array counts towards it.
3) [52,3,5,7]. The last even number in this array is 52 and has index 1. So such an array counts towards it.
I simply don't find a good approach to this problem. In particular, I would be interested in a solution with dynamic programming.
algorithm permutation
edited Nov 24 '18 at 19:55
DaFois
2,01941419
asked Nov 24 '18 at 15:53
ulestaulesta
72
add a comment |
Suppose we have an array of length z. Which consists of x different even numbers and y different odd numbers.
So z = x+y.
We also know that x => 1 always applies.
1st question: How many different arrays of length z there are. That should be exactly z! many or?
2nd question: How many different arrays are there so that the last even number in the array is on an odd index. (The array in this example starts with index 1)
Examples:
1) [1,2,3,4,5] This array has length 5. The last even number in the array is 4 and has index 4 in the array, so we don't count such an array.
2) [52,3,14]. The last even number in this array is 14 and has index 3. So such an array counts towards it.
3) [52,3,5,7]. The last even number in this array is 52 and has index 1. So such an array counts towards it.
I simply don't find a good approach to this problem. In particular, I would be interested in a solution with dynamic programming.
algorithm permutation
edited Nov 24 '18 at 19:55
DaFois
2,01941419
asked Nov 24 '18 at 15:53
ulestaulesta
72
add a comment |
Suppose we have an array of length z. Which consists of x different even numbers and y different odd numbers.
So z = x+y.
We also know that x => 1 always applies.
1st question: How many different arrays of length z there are. That should be exactly z! many or?
2nd question: How many different arrays are there so that the last even number in the array is on an odd index. (The array in this example starts with index 1)
Examples:
1) [1,2,3,4,5] This array has length 5. The last even number in the array is 4 and has index 4 in the array, so we don't count such an array.
2) [52,3,14]. The last even number in this array is 14 and has index 3. So such an array counts towards it.
3) [52,3,5,7]. The last even number in this array is 52 and has index 1. So such an array counts towards it.
I simply don't find a good approach to this problem. In particular, I would be interested in a solution with dynamic programming.
algorithm permutation
edited Nov 24 '18 at 19:55
DaFois
2,01941419
asked Nov 24 '18 at 15:53
ulestaulesta
72
Suppose we have an array of length z. Which consists of x different even numbers and y different odd numbers.
So z = x+y.
We also know that x => 1 always applies.
1st question: How many different arrays of length z there are. That should be exactly z! many or?
2nd question: How many different arrays are there so that the last even number in the array is on an odd index. (The array in this example starts with index 1)
Examples:
1) [1,2,3,4,5] This array has length 5. The last even number in the array is 4 and has index 4 in the array, so we don't count such an array.
2) [52,3,14]. The last even number in this array is 14 and has index 3. So such an array counts towards it.
3) [52,3,5,7]. The last even number in this array is 52 and has index 1. So such an array counts towards it.
I simply don't find a good approach to this problem. In particular, I would be interested in a solution with dynamic programming.
algorithm permutation
algorithm permutation
edited Nov 24 '18 at 19:55
DaFois
2,01941419
asked Nov 24 '18 at 15:53
ulestaulesta
72
edited Nov 24 '18 at 19:55
DaFois
2,01941419
asked Nov 24 '18 at 15:53
ulestaulesta
72
edited Nov 24 '18 at 19:55
DaFois
2,01941419
edited Nov 24 '18 at 19:55
DaFois
2,01941419
edited Nov 24 '18 at 19:55
DaFois
2,01941419
2,01941419
asked Nov 24 '18 at 15:53
ulestaulesta
72
asked Nov 24 '18 at 15:53
ulestaulesta
72
asked Nov 24 '18 at 15:53
ulestaulesta
72
72
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
For the first question:
There are z! arrays unless there are numbers in the array that repeat. The formula is the following:
n!/((n1!)(n2!)(n3!)...(nz!)), where n1 is the number of times the first number in the array repeats, n2 the number of times the second number repeats .. etc.
answered Nov 24 '18 at 16:24
Marko PanushkovskiMarko Panushkovski
111
add a comment |
To answer the second question, we need to look only at the permutations of even/odd sequences:
eee…eeeooo…ooo
`--,--´`--,--´
x y
The number of these where the last e is in an odd position would then only need to be multiplied with the number of permutations amongst the even numbers (x!) and the number of permutations amongst the odd numbers.
So now lets enumerate the e/o permutations:
???????eooo…ooo
`--,--´ `--,--´
i-1 z-i
For some i as the index of the last even number, there are many numbers that begin with a sequence of i-1 digits consisting of x-1 even and y - (z-i) = i-x odd numbers. You should be able the is in a loop, check whether x-1 >= 0 && i-x >= 0 && i-x <= y (valid at all) and whether i is odd, then sum for each of those
(i-1)! / (x-1)! / (i-x)!
answered Nov 24 '18 at 16:46
BergiBergi
374k60565897
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53459852%2fcount-permutation-of-an-array%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
For the first question:
There are z! arrays unless there are numbers in the array that repeat. The formula is the following:
n!/((n1!)(n2!)(n3!)...(nz!)), where n1 is the number of times the first number in the array repeats, n2 the number of times the second number repeats .. etc.
answered Nov 24 '18 at 16:24
Marko PanushkovskiMarko Panushkovski
111
add a comment |
For the first question:
There are z! arrays unless there are numbers in the array that repeat. The formula is the following:
n!/((n1!)(n2!)(n3!)...(nz!)), where n1 is the number of times the first number in the array repeats, n2 the number of times the second number repeats .. etc.
answered Nov 24 '18 at 16:24
Marko PanushkovskiMarko Panushkovski
111
add a comment |
For the first question:
There are z! arrays unless there are numbers in the array that repeat. The formula is the following:
n!/((n1!)(n2!)(n3!)...(nz!)), where n1 is the number of times the first number in the array repeats, n2 the number of times the second number repeats .. etc.
answered Nov 24 '18 at 16:24
Marko PanushkovskiMarko Panushkovski
111
For the first question:
There are z! arrays unless there are numbers in the array that repeat. The formula is the following:
n!/((n1!)(n2!)(n3!)...(nz!)), where n1 is the number of times the first number in the array repeats, n2 the number of times the second number repeats .. etc.
answered Nov 24 '18 at 16:24
Marko PanushkovskiMarko Panushkovski
111
answered Nov 24 '18 at 16:24
Marko PanushkovskiMarko Panushkovski
111
answered Nov 24 '18 at 16:24
Marko PanushkovskiMarko Panushkovski
111
answered Nov 24 '18 at 16:24
Marko PanushkovskiMarko Panushkovski
111
111
add a comment |
add a comment |
To answer the second question, we need to look only at the permutations of even/odd sequences:
eee…eeeooo…ooo
`--,--´`--,--´
x y
The number of these where the last e is in an odd position would then only need to be multiplied with the number of permutations amongst the even numbers (x!) and the number of permutations amongst the odd numbers.
So now lets enumerate the e/o permutations:
???????eooo…ooo
`--,--´ `--,--´
i-1 z-i
For some i as the index of the last even number, there are many numbers that begin with a sequence of i-1 digits consisting of x-1 even and y - (z-i) = i-x odd numbers. You should be able the is in a loop, check whether x-1 >= 0 && i-x >= 0 && i-x <= y (valid at all) and whether i is odd, then sum for each of those
(i-1)! / (x-1)! / (i-x)!
answered Nov 24 '18 at 16:46
BergiBergi
374k60565897
add a comment |
To answer the second question, we need to look only at the permutations of even/odd sequences:
eee…eeeooo…ooo
`--,--´`--,--´
x y
The number of these where the last e is in an odd position would then only need to be multiplied with the number of permutations amongst the even numbers (x!) and the number of permutations amongst the odd numbers.
So now lets enumerate the e/o permutations:
???????eooo…ooo
`--,--´ `--,--´
i-1 z-i
For some i as the index of the last even number, there are many numbers that begin with a sequence of i-1 digits consisting of x-1 even and y - (z-i) = i-x odd numbers. You should be able the is in a loop, check whether x-1 >= 0 && i-x >= 0 && i-x <= y (valid at all) and whether i is odd, then sum for each of those
(i-1)! / (x-1)! / (i-x)!
answered Nov 24 '18 at 16:46
BergiBergi
374k60565897
add a comment |
To answer the second question, we need to look only at the permutations of even/odd sequences:
eee…eeeooo…ooo
`--,--´`--,--´
x y
The number of these where the last e is in an odd position would then only need to be multiplied with the number of permutations amongst the even numbers (x!) and the number of permutations amongst the odd numbers.
So now lets enumerate the e/o permutations:
???????eooo…ooo
`--,--´ `--,--´
i-1 z-i
For some i as the index of the last even number, there are many numbers that begin with a sequence of i-1 digits consisting of x-1 even and y - (z-i) = i-x odd numbers. You should be able the is in a loop, check whether x-1 >= 0 && i-x >= 0 && i-x <= y (valid at all) and whether i is odd, then sum for each of those
(i-1)! / (x-1)! / (i-x)!
answered Nov 24 '18 at 16:46
BergiBergi
374k60565897
To answer the second question, we need to look only at the permutations of even/odd sequences:
eee…eeeooo…ooo
`--,--´`--,--´
x y
The number of these where the last e is in an odd position would then only need to be multiplied with the number of permutations amongst the even numbers (x!) and the number of permutations amongst the odd numbers.
So now lets enumerate the e/o permutations:
???????eooo…ooo
`--,--´ `--,--´
i-1 z-i
For some i as the index of the last even number, there are many numbers that begin with a sequence of i-1 digits consisting of x-1 even and y - (z-i) = i-x odd numbers. You should be able the is in a loop, check whether x-1 >= 0 && i-x >= 0 && i-x <= y (valid at all) and whether i is odd, then sum for each of those
(i-1)! / (x-1)! / (i-x)!
answered Nov 24 '18 at 16:46
BergiBergi
374k60565897
answered Nov 24 '18 at 16:46
BergiBergi
374k60565897
answered Nov 24 '18 at 16:46
BergiBergi
374k60565897
answered Nov 24 '18 at 16:46
BergiBergi
374k60565897
374k60565897
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53459852%2fcount-permutation-of-an-array%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
