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