Comments for Fun with PowerShell - Calculate Permutations at http://www.vmguru.com , comment 1 to 3 out of 3 comments http://www.vmguru.com Sun, 01 Aug 2010 01:50:09 +0100 FeedCreator 1.7.3 http://www.vmguru.com/index.php/articles-mainmenu-62/scripting/101-fun-with-powershell-calculate-permutations#comment-20 In this section only, the traditional definition from combinatorics is used: a permutation is an ordered sequence of elements selected from a given finite set, without repetitions, and not necessarily using all elements of the given set. For example, given the set of letters {C, E, G, I, N, R}, some permutations are ICE, RING, RICE, NICER, REIGN and CRINGE, but also RNCGI – the sequence need not spell out an existing word. ENGINE, on the other hand, is not a permutation, because it uses the elements E and N twice. If n denotes the size of the set – the number of elements available for selection – and only permutations are considered that use all n elements, then the total number of possible permutations is equal to n!, where "!" is the factorial operator. This can be shown informally as follows. In constructing a permutation, there are n possible choices for the first element of the sequence. Once it has been chosen, n − 1 elements are left, so for the second element there are only n − 1 possible choices. For the first two elements together, that gives us n × (n − 1) possible permutations. For selecting the third element, there are then n − 2 elements left, giving, for the first three elements together, n × (n − 1) × (n − 2) possible permutations. Continuing in this way until there are only 2 elements left, there are 2 choices, giving for the number of possible permutations consisting of n − 1 elements: n × (n − 1) × (n − 2) × ... × 2. The last choice is now forced, as there is exactly one element left. In a formula, this is the number n × (n − 1) × (n − 2) × ... × 2 × 1 (which is the same as before because the factor 1 does not make a difference). This number is, by definition, the same as n!. In general the number of permutations is denoted by , , or sometimes , where: n is the number of elements available for selection, and r is the number of elements to be selected (0 ≤ r ≤ n). For the case where r = n it has just been shown that P(n, r) = n!. The general case is given by the formula: As before, this can be shown informally by considering the construction of an arbitrary permutation, but this time stopping when the length r has been reached. The construction proceeds initially as above, but stops at length r. The number of possible permutations that has then been reached is: P(n, r) = n × (n − 1) × (n − 2) × ... × (n − r + 1). So: n! = n × (n − 1) × (n − 2) × ... × 2 × 1 = n × (n − 1) × (n − 2) × ... × (n − r + 1) × (n − r) × ... × 2 × 1 = P(n, r) × (n − r) × ... × 2 × 1 = P(n, r) × (n − r)!. But if n! = P(n, r) × (n − r)!, then P(n, r) = n! / (n − r)!. For example, if there is a total of 10 elements and we are selecting a sequence of three elements from this set, then the first selection is one from 10 elements, the next one from the remaining 9, and finally from the remaining 8, giving 10 × 9 × 8 = 720. In this case, n = 10 and r = 3. Using the formula to calculate P(10,3), In the special case where n = r the formula above simplifies to: The reason why 0! = 1 is that 0! is an empty product, which always equals 1. In the example given in the header of this article, with 6 integers {1..6}, this would be: P(6,6) = 6! / (6−6)! = (1×2×3×4×5×6) / 0! = 720 / 1 = 720. Since it may be impractical to calculate n! if the value of n is very large, a more efficient algorithm is to calculate: P(n, r) = n × (n − 1) × (n − 2) × ... × (n − r + 1). Other, older notations include nPr, Pn,r, or nPr. A common modern notation is (n)r which is called a falling factorial. However, the same notation is used for the rising factorial (also called Pochhammer symbol) n(n + 1)(n + 2)⋯(n + r − 1)r. With the rising factorial notation, the number of permutations is (n − r + 1)r. - itil questions Fri, 25 Sep 2009 22:37:01 +0100 http://www.vmguru.com/index.php/articles-mainmenu-62/scripting/101-fun-with-powershell-calculate-permutations#comment-19 In this section only, the traditional definition from combinatorics is used: a permutation is an ordered sequence of elements selected from a given finite set, without repetitions, and not necessarily using all elements of the given set. For example, given the set of letters {C, E, G, I, N, R}, some permutations are ICE, RING, RICE, NICER, REIGN and CRINGE, but also RNCGI – the sequence need not spell out an existing word. ENGINE, on the other hand, is not a permutation, because it uses the elements E and N twice. If n denotes the size of the set – the number of elements available for selection – and only permutations are considered that use all n elements, then the total number of possible permutations is equal to n!, where "!" is the factorial operator. This can be shown informally as follows. In constructing a permutation, there are n possible choices for the first element of the sequence. Once it has been chosen, n − 1 elements are left, so for the second element there are only n − 1 possible choices. For the first two elements together, that gives us n × (n − 1) possible permutations. For selecting the third element, there are then n − 2 elements left, giving, for the first three elements together, n × (n − 1) × (n − 2) possible permutations. Continuing in this way until there are only 2 elements left, there are 2 choices, giving for the number of possible permutations consisting of n − 1 elements: n × (n − 1) × (n − 2) × ... × 2. The last choice is now forced, as there is exactly one element left. In a formula, this is the number n × (n − 1) × (n − 2) × ... × 2 × 1 (which is the same as before because the factor 1 does not make a difference). This number is, by definition, the same as n!. In general the number of permutations is denoted by , , or sometimes , where: n is the number of elements available for selection, and r is the number of elements to be selected (0 ≤ r ≤ n). For the case where r = n it has just been shown that P(n, r) = n!. The general case is given by the formula: I am doing itil questions and in this course, there are a lot of question of permutation. As before, this can be shown informally by considering the construction of an arbitrary permutation, but this time stopping when the length r has been reached. The construction proceeds initially as above, but stops at length r. The number of possible permutations that has then been reached is: P(n, r) = n × (n − 1) × (n − 2) × ... × (n − r + 1). So: n! = n × (n − 1) × (n − 2) × ... × 2 × 1 = n × (n − 1) × (n − 2) × ... × (n − r + 1) × (n − r) × ... × 2 × 1 = P(n, r) × (n − r) × ... × 2 × 1 = P(n, r) × (n − r)!. But if n! = P(n, r) × (n − r)!, then P(n, r) = n! / (n − r)!. For example, if there is a total of 10 elements and we are selecting a sequence of three elements from this set, then the first selection is one from 10 elements, the next one from the remaining 9, and finally from the remaining 8, giving 10 × 9 × 8 = 720. In this case, n = 10 and r = 3. Using the formula to calculate P(10,3), In the special case where n = r the formula above simplifies to: The reason why 0! = 1 is that 0! is an empty product, which always equals 1. In the example given in the header of this article, with 6 integers {1..6}, this would be: P(6,6) = 6! / (6−6)! = (1×2×3×4×5×6) / 0! = 720 / 1 = 720. Since it may be impractical to calculate n! if the value of n is very large, a more efficient algorithm is to calculate: P(n, r) = n × (n − 1) × (n − 2) × ... × (n − r + 1). Other, older notations include nPr, Pn,r, or nPr. A common modern notation is (n)r which is called a falling factorial. However, the same notation is used for the rising factorial (also called Pochhammer symbol) n(n + 1)(n + 2)⋯(n + r − 1)r. With the rising factorial notation, the number of permutations is (n − r + 1)r. - Matt John Fri, 25 Sep 2009 20:48:52 +0100 http://www.vmguru.com/index.php/articles-mainmenu-62/scripting/101-fun-with-powershell-calculate-permutations#comment-15 FUN! You are assuming that the URL must be a combination of 5 elements out of 62 elements. But AFAIK it is allowed to use an element multiple times, so this would simplify the math to 62^5 which comes down to 916,132,832 different URLs On the second hand, I've seen several 6 character URLs from bit.ly, so I guess their algorythm is somekind different. But I loved the math fun. -Arnim - Arnim van Lieshout Sun, 14 Jun 2009 23:19:29 +0100