Progblemet #3

Ibland kan det finnas anledning att skapa alla möjliga permutationer av element som finns i en lista.

Listan [0,1,2] har följande möjliga permutationer
[[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]]

Som synes kommer en listan med N element ha N! permutationer.

För att jämföra effektiviteten av olika lösningar så kan vi mäta tiden det tar att generera alla möjliga lösningar. För att språk med s.k. lazy-evaluation inte ska optimera bort hela beräkningen måste man använda resultatet.

Så en körning kan se ut något likt detta (från min Ruby lösning nedan), den lista som är helt utskriven är [0,1,2] och den som bara längden är utskriven på är [0,1,2,3,4,5,6,7,8,9]

[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
3628800

Elapsed time: 0m32.751s

Språk som stödjer s.k. list comprehension kan få väldigt korta och eleganta lösningar, men kanske inte speciellt effektiva i vissa lägen. Ett sådan exempel är Erlang där man kan lösa detta exempel med väldigt lite kod

% The permutations of an empty list is a list with a single empty list   
perms([]) ->
    [[]];
% Permutations of a non-empty list is created by concatenate each
% element in the list with every permutation of the rest of the list
% with the element used as head removed.
perms(L)  ->
    [[Head|Tail] || Head <- L, Tail <- perms(L -- [Head])].

io:fwrite("~w~n", [perms([0,1,2])]).
io:fwrite("~w~n", [length(perms(lists:seq(0,9)))]).

Den andra lösningen är i Ruby som inte stödjer list comprehension men ändå har bra stöd för att jobba med listor via map, select (filter).

def perms(l)
  if l.empty?
    [[]]
  else
    l.map{|head| perms(l.select{|e| head!=e}).map{|e|[head]+e}}.flatten(1)
  end
end

puts perms((0..2).to_a).to_s
puts perms((0..9).to_a).length

Har inte hunnit testa detta i språk som C eller C++ och om tiden det tar generera alla permutationer är <1s så lägg till resultatet för det antal element som gör att beräkningen överstiger i alla fall 1s.

Edit: litet förtydligande. En lista/array/vektor eller liknande med ALLA permutationer ska alltså finnas i RAM när perms (eller vad ni kallar den) funktionen retunerar. Så det räcker inte enbart med att köra std::next_permutation i C++ och bara räkna antal varv, varje permutation måste även sparas för att göra det till en så äpplen mot äpplen jämförelse som möjligt mellan språken.

Och den observante har nog redan noterat att mina lösningar var typiska divide-and-conquer så för den som vill vara lite mer avancerad så finns det potential till massor med parallellism för att accelerera detta över flera CPU-kärnor.

Ok, ska försöka förklara problemet på svenska

Målet med detta problem är att skriva ett program som räknar ut alla olika sätt du kan ordna N st unika objekt.

Om vi har bokstäverna A,B,C på hur många många sätt kan jag ordna dessa?

Svaret är:

1. A B C

2. A C B

3. B A C

4. B C A

5. C A B

6. C B A

d.v.s. 6 olika sätt. Men detta kanske var lite svårare än vad jag hade tänkt mig, trots att man kan skriva ganska kompakta lösningar i många språk.

Kan i alla fall lägga till en Python version

# coding: utf-8                                                                                 
# Ger en lista av alla permutationer av listan L                                                
def perms(L):
     if len(L) == 0:
          # En tom lista ger endast ett resultat: en tom lista...                               
          return [[]]
     # ...annars, skapa en lista där varje element i L är i första                              
     # positionen och addera varje permutation av resterande element                            
     # till detta element. Det rekursiva anropet till 'perms' sker med                          
     # en lista som har alla element utom Head.                                                 
     return [[Head] + Tail for Head in L for Tail in perms(list(set(L) - set([Head])))]

print perms(range(3))
print len(perms(range(10)))

Och här är en version i C++11. Denna var ganska väntat den snabbaste så här långt, men ett problem här är att det inte längre finns något enkelt sätt att förändra problemet så det effektivt kan köra på många CPU-kärnor.

Ska försöka få tid till att sätta ihop en version i plain old C som utan problem kan använda alla 8 CPU-trådar på en Core i7. Är lite stressigt denna vecka, har deadlines att fixa inför nästa vecka

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

// Detta är bara så att man enkelt kan skicka en lista till 'cout'
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "[ ";
    for (auto &e: v)
        os << e << ' ';
    os << ']';
    return os;
}

// Att retunera stora strukturer "by-value" är alltid billigt i C++11, så det blir INTE
// en kopiering av den gigantiska vector som kommer tillbaka som svar när man
// skickar in 'v2'
vector<vector<int> > perms(vector<int> &v)
{
    vector<vector<int> > res;

    sort(begin(v), end(v));
    do {
        res.push_back(v);
    } while (next_permutation(begin(v), end(v)));

    return res;
}

int main(int argc, char *argv[])
{
    vector<int> v1(3);
    // iota är det närmaste man kommer "range" i python och (N to M) i 
    // språk som Scala och Ruby första elementet blir 0 (3:e argumentet) 
    // och varje nästa element blir (föregående element + 1)
    iota(begin(v1), end(v1), 0);

    vector<int> v2(10);
    iota(begin(v2), end(v2), 0);

    cout << perms(v1) << endl;
    cout << perms(v2).size() << endl;

    return 0;
}

[ [ 0 1 2 ] [ 0 2 1 ] [ 1 0 2 ] [ 1 2 0 ] [ 2 0 1 ] [ 2 1 0 ] ]
3628800

[ [ 0 1 2 ] [ 0 2 1 ] [ 1 0 2 ] [ 1 2 0 ] [ 2 0 1 ] [ 2 1 0 ] ]
39916800

Edit:
Det man ska komma ihåg här är att detta problem alltså har en tids och storlekskomplexitet som är proportionellt mot fakulteten av listan man stoppar in. Så en lista med 11 element (0..10) har alltså 11!=39916800 unika kombinationer. Att spara denna lista tar som absolut minimum 40M*4(4 bytes för en int)*11=~1.8GB RAM... Så man inser snabbt att RAM kommer ta slut om man skickar inte lite större listor

Vet hur det är, har haft väldigt tight med tid överhuvudtaget den senaste veckan. Har börjat på en C version som är tillräckligt parallell för att utan problem använda alla de 8 trådar en Core i7:a har.

Kan i alla fall posta en Clojure version då detta språk, som vanligt, gör det väldigt enkelt att lösa problemet.

(defn perms[List]
  (if (empty? List)
    '(())
    (for [Head List
          Tail (perms (filter (partial not= Head) List))]
      (cons Head Tail))))

(println (perms (range 3)))
(println (count (perms (range 10))))

Börjar bli dax för ett nytt problem och ska tänka ut något relativt enkelt denna gång då det ser ut att vara tjockt även denna vecka.

Har ju skrivit tidigare att det går att använda flera CPU-trådar för att lösa detta problem. Tänkte först göra en sådan lösning i C, men tänkte om då jag faktiskt sitter med C hela dagarna på jobbet och en anledning till att jag överhuvudtaget tycker det är intressant att lägga tid på sådana här saker är att det ger en möjlighet att lösa uppgifter på sätt som man normalt sett kanske inte gör.

Så det blir ingen lösning av detta i C, har nog av den varan på jobbet. Valde i stället att göra en lösning i Go som kan använda flera CPU-trådar

Är definitivt ingen Go-expert, men Go verkar vara ett språk som är riktigt genomtänkt. Go är designat efter att vara enkelt, man har inte funderat på vilka features man kan lägga till (vilket man gjort rätt mycket i språk som C++ och C#, något som resulterar i ENORMA språk) utan hur mycket man kan ta bort utan att för den delen göra den svårt att uttrycka sig i språket.

Go är nästan lika effektivt som C/C++ och likt Erlang så är det väldigt enkelt att skriva program som hanterar massiva mängder I/O i Go.

Antar att Go är ganska nytt för de flesta så har stoppat in lite kommenterar. En kanal "channel" i Go är en stark typad kommunikationskanal som kan användas för att kommuncera på ett säkert och korrekt sätt mellan s.k. go-routines. En go-routine mappas INTE mot en OS-tråd, utan Go har en egen schemaläggare som skapar "ett lämpligt" antal OS-trådar och lägger sedan ut de go-routiner man har på dessa. En "go-routine" kostar bara några 100-bytes i overhead, så det är möjligt att ha många tusen av dessa. En OS-tråd tar typiskt ett par MB, så systemet mår inte bra om man har 1000-tals av dessa.

Om jag har en kanal med namnet 'ch' av typen int så kan man skriva till kanalen på detta sätt

ch<- 123
var x int = 1234
ch<- x

och man kan läsa ur den på detta sätt

var y int
y <-ch
fmt.Println("Nästa värde i kanalen är", <-ch)

range i Go gör så man kan traversera arrayer. För varje element får man ett par där det första elementet är index i arrayen och det andra elementet är värdet. Är man inte intresserade av något av elementen talar man om det genom att tilldela det elementet till '_' . Go tillåter inte att man inför variabler man inte använder!

package main

import "fmt"

func fac(n int) int {
    if n <= 1 {
        return 1
    }
    return n * fac(n-1)
}

// Returns a new list where the element at index 'idx' is removed             
func disassoc(List []int, idx int) []int {
    nl := make([]int, len(List) - 1)
    copy(nl, List[:idx])
    copy(nl[idx:], List[idx+1:])
    return nl
}

// Single threaded version of "perms"                                         
func perms_worker(List []int) [][]int {
    if (len(List) <= 1) {
        return [][]int{List}
    }

    ret := [][]int{}
    for hidx, Head := range(List) {
        for _, Rest := range(perms_worker(disassoc(List, hidx))) {
            ret = append(ret, append(Rest, Head))
        }
    }
    return ret
}

// Creates len(List) independent go-routines that calculates all              
// permutations for the subset where one elements value and position          
// is fixed                                                                   
func perms(List []int) [][]int {
    // The answers from the go-routins will be recevied through this          
    // channel                                                                
    perm_ch := make(chan [][]int)

    // Start the go-routines                                                  
    for i, _ := range(List) {
        go func(idx int) {
            perm_ch<- perms_worker(disassoc(List, idx))
        }(i)
    }

    // Total number of answers will be the faculty of the list length.        
    acc := make([][]int, fac(len(List)))
    // Each sub-problem will generate fac(len(List) - 1 permutations,         
    // so use that as the stride when copy the solutions into the             
    // result array.                                                          
    stride := fac(len(List) - 1)
    for i, Head := range(List) {
        slice := acc[i*stride:(i+1)*stride]
        copy(slice, <- perm_ch)
        for j, Rest := range(slice) {
            slice[j] = append(Rest, Head)
        }
    }
    return acc
}

func main() {
    fmt.Println(perms([]int{0,1,2}) )
    fmt.Println(len(perms([]int{0,1,2,3,4,5,6,7,8,9})))
}

Att det inte alls skalar linjärt beror dels på att go-routines är inte optimerade för CPU-bundna laster utan optimerade för I/O. Men kanske än viktigare är att det kopieras rejält med data över kanalen perm_ch och det blir nog en flaskhals i L3 cache och på RAM-bussen, detta är också anledning varför denna version inte alls är lika snabb som den i C++.

Går totalt sett x2.7 gånger snabbare när alla CPU-trådarna används jämfört med att bara använda en CPU-tråd.

Edit: och bara för referens mot de andra implementationerna så är här en enkeltrådad variant i Go

package main

import "fmt"

func disassoc(List []int, idx int) []int {
    nl := make([]int, len(List) - 1)
    copy(nl, List[:idx])
    copy(nl[idx:], List[idx+1:])
    return nl
}

func perms(List []int) [][]int {
    if (len(List) <= 1) {
        return [][]int{List}
    }

    ret := [][]int{}
    for hidx, Head := range(List) {
        for _, Rest := range(perms(disassoc(List, hidx))) {
            ret = append(ret, append(Rest, Head))
        }
    }
    return ret
}

func main() {
    fmt.Println(perms([]int{0,1,2}) )
    fmt.Println(len(perms([]int{0,1,2,3,4,5,6,7,8,9})))
}

perms :: Eq a => [a] -> [[a]]
perms [x] = [[x]]
perms xs = [ x : rest | x <- xs, rest <- perms (xs \\ [x]) ]

main :: IO ()
main = print (perms [1..9])

Fungerade din version i Haskell? Vilken kompilator körde du med då? Tänkte bl.a. på att '\\' tillhör modulen "Data.Set" som inte är importerad.
Med följande förändringar lyckades jag köra det hela i alla fall

perms :: Eq a => [a] -> [[a]]
perms [] = [[]]
perms xs = [ x : rest | x <- xs, rest <- perms (filter (\e -> x /= e) xs) ]

main :: IO ()
main = do
  print (perms [0..2])
  print (length (perms [0..9]))