RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved list searches and permutations. (Note that this ends today.)

Task 1: Consecutive Sequence

You are given an unsorted array of integers, @ints.

Write a script to return the length of the longest consecutive elements sequence. Return -1 if none found. The algorithm must runs in O(n) time.

Exhaustive search of the sorted array seems to be the trick here. In Raku:

sub consecutivesequence(@a) {

Get the sorted array and initialise various counters.

    my @b = @a.sort({$^a <=> $^b});
    my $mxlen = 0;
    my $here = 0;
    loop {

Look from one entry after the current ($here), to potentially as far as the end.

        for ($here + 1) .. @b.end -> $there {

If it isn't part of the sequence that started at $here, note that sequence and start from this point next time..

            if @b[$there] != $there - $here + @b[$here] {
                $mxlen = max($mxlen, $there - $here);
                $here = $there;
                last;
            }

If we got to the end without a non-sequence number, note that.

            if $there == @b.end {
                $mxlen = max($mxlen, $there - $here + 1);
                $here = $there;
                last;
            }
        }

If we've got to the end, exit.

        if $here >= @b.end {
            last;
        }
    }

And if the longest sequence is 1 (every number on its own is a sequence of 1), return -1 as requested.

    if $mxlen < 2 {
        $mxlen = -1;
    }
    $mxlen;
}

Task 2: Next Permutation

You are given an array of integers, @ints.

Write a script to find out the next permutation of the given array.

The next permutation of an array of integers is the next lexicographically greater permutation of its integer.

In the languages with built-in permutation routines, that's the order in which they produce them, but the routine I wrote implementing Heap's algorithm doesn't… so I sort the result.

Rust, which does have a permuter:

use itertools::Itertools;

fn nextpermutation(a: Vec<u32>) -> Vec<u32> {

Start with a sorted copy of the list.

    let mut b = a.clone();
    b.sort();
    let mut flag = false;
    let mut out: Vec<u32> = Vec::new();

Look through the permutations.

    for px in b.iter().permutations(b.len()) {
        let py = px.iter().copied().copied().collect::<Vec<u32>>();

If we don't have a result at all, stick in the first one. (Because we're only going to look through this list once.)

        if out.len() == 0 {
            out = py.clone();
        }

If the previous pass set the flag, use this result.

        if flag {
            out = py.clone();
            break;
        }

If we have a match, set the flag for the next pass.

        if py == a {
            flag = true;
        }
    }
    out
}

So most of the time the loop finds a match to the input, sets the flag, then on the next loop sets the next entry. But if the match was on the last entry, that won;t work, so we pre-seed the output with the first entry.

Kotlin needs a sorter, which ends up looking like:

    val listComparator = Comparator {
        i: List<Int>, j: List<Int> ->
            var ix = 0
        var res = false
        while (true) {
            if (ix >= i.size && ix >= j.size) {
                break
            }
            if (ix < i.size && ix >= j.size) {
                res = true
                break
            }
            if (ix >= i.size && ix < j.size) {
                res = false
                break
            }
            if (i[ix] != j[ix]) {
                res = i[ix] < j[ix]
                break
            }
            ix += 1
        }
        if (res) {
            -1
        } else {
            1
        }
    }
    for (px in permute(b).sortedWith(listComparator)) {

(etc. as before)

Full code on github.