permute2.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;
}


// partitioning between tasks heuristic

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




// if I used this function as auxilarly in the permute iter functions 
// I got segmentation fault.






// 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(arr, arrFinal) {
    yield arr;
    while true {
        var i = arr.numElements;
        while i > 1 && arr[i - 1] >= arr[i] {
            i = i - 1;
        }

        if isEqual(arr, arrFinal) {
            return;
        }

        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;
        }  
        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, arrFinal)
    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, tid);    // now every follower needs to generate permutations       
    }                                                   // between these two limits    
}

iter permute(param tag: iterKind, arr, arrFinal, 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 { yield arr; }
    while true {
        var i = arr.numElements;
        while i > 1 && arr[i - 1] >= arr[i] {
            i = i - 1;
        }
        if isEqual(arr, arrfinal) {
            return;
        }
        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;
        }  
        yield arr;
    }
}

forall i in permute([1,2,3,4,5], [5,4,3,2,1]) {     // parallel    
    writeln(i);                         
}    

for i in permute([1,2,3,4,5],[5,4,3,2,1]) {       // serial
    writeln(i);
}