permutations.chpl

use Sort;

var sentialPermutation = [42];


// return true if the two arrays are equal

proc isEqual(a, b) : bool {
    for (i, j) in zip(a,b) {
        if i != j {
            return false;
        }
    }
    return true;
}



// we need to get ALL the permutations of [1,2,3,4,5] so we know
// that if we generate them in lexicographical order we would have
// [1, 2, 3, 4, 5] as the first permutation and [5, 4, 3, 2, 1] as the last permutation
// the partition function do the following:
// assume we have 4 tasks we need to distribute the whole lexicographical range of all permutations
// into 4 intervals. so assume we insert arr to be [1,2,3,4,5] and numOfTasks to 4 tasks
// we have in return the following array of arrays
// [1,2,3,4,5]---
//               ---- for task number 1 to generate
// [1,2,3,5,4]---
//               ---- for task number 2 to generate
// [1,2,5,4,3]---
//               ---- for task number 3 to generate
// [1,5,2,4,3]---
//               ---- for task number 4 to generate
// [5,1,2,4,3]---
//               ---- for task number 5 to generate
// [5,4,3,2,1]---

// it works for arbitrary length of arrays and number of tasks



proc partition(arr, numOfTasks) {
    var length = arr.numElements;
    var step = length / numOfTasks;
    var partitions: [1..numOfTasks+1] [1..length] int;
    var j = length;
    var i = 1;
    partitions[i] = arr;
    while j > 1 && i < numOfTasks {
        arr[j] <=> arr[j - step];
        j -= 1;
        i += 1;
        partitions[i] = arr;
    }
    i += 1;
    sort(arr, comparator=reverseComparator);
    partitions[i] = arr;
    return partitions;
}


// you feed this function arr to get the next lexicographic permutation
// we pass arrFinal to be able know when to stop


proc next_permutation(in arr, in arrFinal) {        

    // non-increasing suffix

    var i = arr.numElements;
    while i > 1 && arr[i - 1] >= arr[i] {
        i = i - 1;
    }

    if isEqual(arr, arrFinal) {
        return sentialPermutation;
    }

    var j = arr.numElements;
    while arr[j] <= arr[i - 1] {
        j = j - 1;
    }

    arr[i - 1] <=> arr[j];

    // sort the suffix
    j = arr.numElements;
    while i < j {
        arr[i] <=> arr[j];
        i = i + 1;
        j = j - 1;
    }  
    return arr;
}

// for serial permutation ... works very well

iter permute(in arr) {
    var firstPermutation = arr;
    sort(firstPermutation);
    var lastPermutation = arr;
    sort(lastPermutation, comparator=reverseComparator);
    yield firstPermutation;
    var nowPermutation = next_permutation(firstPermutation, lastPermutation);
    while !isEqual(nowPermutation, sentialPermutation) {
        yield nowPermutation;
        nowPermutation = next_permutation(nowPermutation, lastPermutation);
    }
}

// here we the first permutation and assume it is sorted and the job of the leader iterator 
// is to "partition" and pass the appropiate permutations to the followers through followThis
// tuple. 

iter permute(param tag: iterKind, arr)
    where tag == iterKind.leader {
    var numOfTasks = here.maxTaskPar;                   // it works in forall loop if we make numOfTasks 1
    var partitions = partition(arr, numOfTasks);        // otherwise the behavior of forall loop is undeterminstric and change for every run
    coforall tid in 1..#numOfTasks {
        var firstPermutation = partitions[tid];
        var secondPermutation = partitions[tid+1];
        yield (firstPermutation, secondPermutation);    // now every follower needs to generate permutations       
    }                                                   // between these two limits    
}

iter permute(param tag: iterKind, arr, followThis) 
    where tag == iterKind.follower && followThis.size == 2 {
    var startPermutation = followThis(1);               // this is the starting permutation
    var finishPermutation = followThis(2);              // this is the last permutation
    yield startPermutation;
    startPermutation = next_permutation(startPermutation, finishPermutation);
    while true {
        yield startPermutation;
        startPermutation = next_permutation(startPermutation, finishPermutation);
        if isEqual(startPermutation, sentialPermutation) { return; }
    }
}

forall i in permute([1,2,3,4,5]) {      // if we made numOfTasks equals to 1, it works as if we used
    writeln(i);                         // serial iterators. otherwise it behavior changes every time
}                                       

// for i in permute([1,2,3,4]) {        ====> this works
//     writeln(i);
// }

// var partitions = partition([1,2,3,4,5], 4)  ===> behaves as expected

for serial permutation where you are

iter permute(in arr) {
var firstPermutation = arr;
   sort(firstPermutation);
    var lastPermutation = arr;
    sort(lastPermutation, comparator=reverseComparator);
    yield firstPermutation;
    var nowPermutation = next_permutation(firstPermutation, lastPermutation);
    while !isEqual(nowPermutation, lastPermutation) {
        yield nowPermutation;
        nowPermutation = next_permutation(nowPermutation, lastPermutation);
    }
}

if I use last permutation I dont reach an error halt in that case , Since it is trying to assigning differnt types of arrays , maybe is is linked to
issues chapel-lang/chapel#10497
if I try the your code of serial with --no-bounds , It inturn falls into segmentation falt.

oh thank you very much.
I will try to fix that first, and hopefully, things get fixed in parallel iterators. I think that It explains that non-deterministic output of it. Thank you again.