Recently I've been working on some computational geometry code, and noticed that Phobos doesn't have any equivalent of STL's next_permutation. I saw there were some discussions about this back in 2010 -- did anything come of it?
If there is any interest in next_permutation, I'd also like to propose a next_even_permutation for ranges without duplicate elements. There is a simple way of extending Narayana Pandita's in-place algorithm for enumerating all permutations such that only even permutations are returned. // Also, I'm interested in Cartesian products of n ranges. Cartesian products tend to be too long to explicitly construct, so it lends itself perfectly to a range interface where the elements of the product are computed on the fly. Now I saw in the dlang.org search results that Cartesian products have been discussed before, but got roadblocked because the naïve implementation of Cartesian product (simply enumerate the first range, then popFront the second range when the first runs out and gets restored to the initial .save point, etc.) doesn't lend itself well to infinite ranges. Here's my proposed solution: we can use a trick that mathematicians use in set theory to prove that the cardinality of the rationals is equal to the cardinality of the natural numbers. Make a table of infinite width and height, with rows representing one copy of the natural numbers and columns another copy, then enumerate all elements by enumerating diagonals. This produces a one-to-one correspondence between the natural numbers and pairs of natural numbers, of which the rationals are a subset (thus one has |N| ≤ |Q| ≤ |N|, proving that |N| = |Q|). For ranges, we don't care about eliminating duplicates like 2/4 = 1/2, since we want all possible pairs. So the infinite table looks like: (0,0) (1,0) (2,0) (3,0) (4,0) ... (0,1) (1,1) (2,1) (3,1) ... (0,2) (1,2) (2,2) ... (0,3) (1,3) ... (0,4) ... ... The diagonals are therefore: (0,0) (0,1) (1,0) (0,2) (1,1) (2,0) (0,3) (1,2) (2,1) (3,0) (0,4) (1,3) (2,2) (3,1) (4,0) ... The characteristic of the n'th diagonal is that the sum of elements in each diagonal is equal to n. For example, the zeroth diagonal has only (0,0) since that's the only pair that sums to 0. The first diagonal is (0,1), (1,0): each pair sums to 1. The second diagonal: each pair sums to 2, and so on. The general form for the i'th element of the n'th diagonal is therefore (i, n-i), for 0 ≤ i ≤ (n-1). So to enumerate the Cartesian product of two infinite ranges, we enumerate its diagonals by interpreting the above pairs as indices into the respective ranges. So, the first range can be a forward range and the second bidirectional (since for each diagonal we need to enumerate the second range from the n'th element down to the first). Of course, if the first range is bidirectional and the second is forward, we can just swap them and reverse the pairs generated. If one or both of the ranges is finite, then we can fall back to the naïve method of enumerating the Cartesian product, in which case we can relax the requirement on the ranges to be just one forward range and one input range (with the infinite range being the input range, if one of them is infinite). To support the Cartesian product of n ranges, we just compose multiple binary Cartesian products. Comments? :) T -- Many open minds should be closed for repairs. -- K5 user