next_permutation and cartesian product for ranges?

[H. S. Teoh]

On Tue, Oct 09, 2012 at 05:46:41PM -0400, Andrei Alexandrescu wrote:
> On 10/9/12 4:46 PM, H. S. Teoh wrote:
> >On Tue, Oct 09, 2012 at 02:25:13PM -0400, Andrei Alexandrescu wrote:
> >>On 10/9/12 1:52 PM, H. S. Teoh wrote:
> >[...]
> >>>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.
> >>
> >>Yes, we need next_permutation. It will be up to you to convince the
> >>Grand Inquisition Committee of Reviewers that next_even_permutation
> >>is necessary and/or sufficient.
> >
> >Is there much chance of this, if the algorithm only works correctly
> >when the input array has no duplicate elements? AFAIK there's no easy
> >way to ensure unique elements without introducing runtime checks.
> 
> We draw the line at memory safety. If you must assume distinct
> elements and state that assumption, you're fine as long as you don't
> transgress into unsafe. One alternative would be to run a O(N) check
> with probability 1/N, trick that assumeSorted() does.

The algo will never transgress into unsafe. It's just that it will
produce incomplete results if the array has duplicate elements (it will
fail to produce some permutations).


[...]
> >>Yah, I call that the Cantor's diagonalization trick - I reckon
> >>that's how he proved there are more reals than rationals:

Actually, this one is to prove that |Q|=|N|. The more famous Cantor
diagonalization is the one where he proves that the reals are
uncountable. But actually, that proof wasn't the original proof; it was
something that came later. The original proof used a different method.
In any case, I think we don't have to worry about Cartesian products of
uncountable ranges. :-P


> >>http://goo.gl/MTmnQ. We need that badly. Please implement pronto and
> >>let us destroy you for having done so.

Please see other post.


[...]
> >// I wrote this 'cos I needed it. Why isn't it in std.range?
> >// A better name for this is probably "denest" or "denestOne", since it doesn't
> >// really flatten arbitrarily-nested ranges.
> >auto flatten(R)(R ror)
> 
> crossProduct.

I was an idiot. I knew about std.algorithm.joiner but for some reason
didn't think of it at the time. In any case, crossProduct doesn't make
any sense to me... I don't see what it's got to do with flattening
nested ranges.


> >	if (isInputRange!R&&  isInputRange!(ElementType!R))
> 
> Tab detected. System overload

// vim:set ts=4 sw=4 expandtab:

:-)


T

-- 
Always remember that you are unique. Just like everybody else. -- despair.com