When implementing my code as native C without using any AEDesc and AEDescList types (and their associate functions) but simple array of int values, it’s done in 15 ms on an old MacBook Pro from 2011. So the delay in my OSAX is really handling and copying AppleEvent descriptors. But I was cheating, I only swapped and printed them (and ignoring the results). In my second attempt I have created an int ** to lookup performance differences.
The results were that it took 30ms to actually find every permutation for a list of 9 items and copy them to an listed list of arrays (or array of pointer pointers). in that case someone could really do something with the results for later processing. I also tried to find the permutations of a list of 11 integers. It comes back with a list containing almost 40 million permutations (39,916,800 to be excactly) just under 4 seconds.
Anyway, if anyone is interested in the code:
//
// main.c
// permutation
//
// Created by Bastiaan on 07-10-14.
// Copyright (c) 2014 All rights reserved.#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void printPermutations(int **allPermutations, int index, int len);
void permute(int * theList, int begin, int end, int **allPermutations, int*allPermutationLen);
void swapItems (int *itemA, int *itemB);int main(int argc, const char * argv[])
{
// variables needed to time the elapsed time
clock_t startTime;
clock_t endTime;
clock_t time_spent;[color=#AA0D91]int[/color] listSize = [color=#1C00CF]11[/color]; [color=#007400]//change this value to size of list to permutate[/color] [color=#AA0D91]int[/color] *theList = [color=#2E0D6E]malloc[/color]([color=#AA0D91]sizeof[/color]([color=#AA0D91]int[/color]) *listSize); [color=#AA0D91]int[/color] **allPermutations; [color=#AA0D91]int[/color] allPermutationSize = [color=#1C00CF]1[/color]; [color=#007400]//how big will the list be[/color] [color=#AA0D91]int[/color] allPermutationLen = [color=#1C00CF]0[/color]; [color=#007400]//wat what current position are we[/color] [color=#007400]// calulate the size needed to store all permutations[/color] [color=#AA0D91]for[/color] ([color=#AA0D91]int[/color] i = [color=#1C00CF]1[/color];i < listSize +[color=#1C00CF]1[/color]; i++) allPermutationSize = allPermutationSize * i; [color=#007400]// allocate the memory needed to store linear all pointers[/color] [color=#007400]// to every possible permutation. This will avoid the flooding[/color] [color=#007400]// of reallocations otherwise is needed.[/color] allPermutations = [color=#2E0D6E]malloc[/color]([color=#AA0D91]sizeof[/color]([color=#AA0D91]int[/color] *) * allPermutationSize); [color=#007400]// create a list of integers starting from 1 to ...[/color] [color=#AA0D91]for[/color] ([color=#AA0D91]int[/color] i =[color=#1C00CF]0[/color];i<listSize;i++) theList[i] = i; [color=#007400]// get start time[/color] startTime = [color=#2E0D6E]clock[/color](); [color=#007400]//start permutation[/color] [color=#26474B]permute[/color](theList, [color=#1C00CF]0[/color], listSize -[color=#1C00CF]1[/color], allPermutations, &allPermutationLen); [color=#007400]// get stop time[/color] endTime = [color=#2E0D6E]clock[/color](); [color=#007400]// subtract the start to finish time to get the elapsed time in milliseconds[/color] time_spent = (endTime - startTime) / ([color=#643820]CLOCKS_PER_SEC[/color] / [color=#1C00CF]1000[/color]); [color=#007400]//print to stdout the eleapsed tim in milliseconds[/color] [color=#2E0D6E]printf[/color]([color=#C41A16]"Execution took %li ms\n"[/color], time_spent); [color=#007400]//print number of permutations[/color] [color=#2E0D6E]printf[/color]([color=#C41A16]"Number of permutations are %i items\n"[/color], allPermutationSize); [color=#007400]//print first and last permutation just for checking[/color] [color=#26474B]printPermutations[/color](allPermutations, [color=#1C00CF]0[/color], listSize); [color=#26474B]printPermutations[/color](allPermutations, allPermutationSize -[color=#1C00CF]1[/color], listSize); [color=#007400]// actually we should free memory here, but we reached end of program[/color] [color=#AA0D91]return[/color] [color=#1C00CF]0[/color];
}
void printPermutations(int **allPermutations, int index, int len)
{
for (int i = 0; i < len; i++) {
printf(“%i”, allPermutations[index][i]);
if (i == (len -1)){
[color=#2E0D6E]printf/color;
} else {
printf(", ");
}
}
}void permute(int * theList, int begin, int end, int **allPermutations, int*allPermutationLen)
{
// check if we’re at the last item in the list
if (begin == end){
// We’re at the last item in the list, it reached
// reached the bottom level in the recursion. Copy
// the current state of theList to allPermutations[color=#007400]// allocate a new array[/color] [color=#AA0D91]int[/color] * item = [color=#2E0D6E]malloc[/color]([color=#AA0D91]sizeof[/color]([color=#AA0D91]int[/color]) * (end+[color=#1C00CF]1[/color])); [color=#007400]// copy each item of the current state of theList to theItem[/color] [color=#AA0D91]for[/color] ([color=#AA0D91]int[/color] i =[color=#1C00CF]0[/color]; i < end+[color=#1C00CF]1[/color]; i++) { item[i] = theList[i]; } [color=#007400]// save a pointer to 'item' and save it in the[/color] [color=#007400]// allPermutation array and increment insertion[/color] [color=#007400]// point allPermutationLen by 1[/color] allPermutations[(*allPermutationLen)++] = item; } [color=#AA0D91]else[/color] { [color=#007400]//begin a loop to loop through all remaining items[/color] [color=#AA0D91]for[/color] ([color=#AA0D91]int[/color] i = begin;i < end+[color=#1C00CF]1[/color];i++){ [color=#007400]//only swap when needed[/color] [color=#AA0D91]if[/color] (i != begin) [color=#007400]// swap item with first remaining item[/color] [color=#26474B]swapItems[/color]((theList +i), (theList + begin)); [color=#007400]// call me again but this time start with the next item in theList[/color] [color=#26474B]permute[/color](theList, begin +[color=#1C00CF]1[/color], end, allPermutations, allPermutationLen); [color=#007400]// only swap back when swapped before[/color] [color=#AA0D91]if[/color] (i != begin) [color=#007400]// swap back, the next loop has to begin with[/color] [color=#007400]// theList in the same order as we started the function[/color] [color=#26474B]swapItems[/color]((theList +i), (theList + begin)); } }
}
void swapItems (int *itemA, int *itemB)
{
// Swap: create a temporary container,
// copy value of itemA to itemX, copy value itemB to itemA (overwrite) and
// then copy tmp to y.[color=#AA0D91]int[/color] itemX; itemX = *itemA; *itemA = *itemB; *itemB = itemX;
}