generating permutations in lexicographic order in serial and parallel fashion

example4Permutations.chpl

use Sort;

// partitioning between tasks algorithms

// 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.size;
    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;
}




iter permute(arr) {
    sort(arr);
    var arrFinal = arr;
    sort(arrFinal, comparator=reverseComparator);
    yield arr;
    while true {
        var i = arr.size;
        while i > 1 && arr[i - 1] >= arr[i] {
            i = i - 1;
        }

        if arr.equals(arrFinal) {
            return;
        }

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

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

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

// 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 {
    sort(arr);
    var numOfTasks = here.maxTaskPar;                   
    var partitions = partition(arr, numOfTasks);        
    coforall tid in 1..#numOfTasks {
        
        var firstPermutation = partitions[tid];
        var secondPermutation = partitions[tid+1];
        writeln(tid,"=====>", firstPermutation,"===>", secondPermutation);      // for debugging
        yield (firstPermutation, secondPermutation, tid);    // now every follower needs to generate permutations       
    }                                                        // between these two limits    
}

iter permute(param tag: iterKind, arr, followThis) 
    where tag == iterKind.follower && followThis.size == 3 {
    var arr = followThis(1);               // this is the starting permutation
    var arrFinal = followThis(2);              // this is the last permutation
    var tid = followThis(3);
    if tid == 1 then yield arr;
    if tid == here.maxTaskPar then sort(arrFinal, comparator=reverseComparator);         // this looks really ugly
    while true {
        var i = arr.size;
        while i > 1 && arr[i - 1] >= arr[i] {
            i = i - 1;
        }
        if arr.equals(arrFinal) {
            return;
        }
        var j = arr.size;
        while arr[j] <= arr[i - 1] {
            j = j - 1;
        }
        arr[i - 1] <=> arr[j];
        // sort the suffix
        j = arr.size;
        while i < j {
            arr[i] <=> arr[j];
            i = i + 1;
            j = j - 1;
        }  
        yield arr;
    }
}

forall i in permute([1,2,4,6,3,9,14,13]) {     // parallel    
    writeln(i);                         
}    

MUST be compiled with Chapel version < 1.22 ... because It assumes arrays are 1-indexed not 0-indexed