[Conny Westh]

Jag sitter och sliter mitt hår för jag har en liten otrevlig bugg som jag bara inte kan se, trots att det är ett enkelt matematiskt problem jag försöker lösa. Möjligen är min hjärna för trött för att fungera just nu....

Jag försöker åstadkomma kombination av alla möjliga kombinationer av array med integer.

När jag tar ut fakulteten av 3 dvs 3! ska det resultera i 6 olika möjliga permutationer (en permutation är ju en kombination där även ordningen har betydelse).

Jag får ut 5 permutationer mot förväntade 6. Någon som har bättre koll på matematiken som kan se vad jag gör för fel.

Jag har kollat på många webbsidor med detta matematiska problem så det finns många som har löst det.

Men nu har jag försökt med min enkla lilla algoritm men kört i diket.

' Fil: Module1.bas
' VB.NET
Module Module1
 * *Sub Main()
 * * * *Dim x As New Permutation()
 * * * *x.start()
 * *End Sub
End Module

' Fil: Permutation.cls
' VB.NET
Public Class Permutation
 * *Private arr() As Integer = {1, 2, 3} ' Ska bli 3! dvs 6 rader
 * *'Private arr() As Integer = {1, 2, 3, 4} ' Ska bli 4! dvs 24 rader
 * *'Private arr() As Integer = {1, 2, 3, 4, 5} ' Ska bli 5! dvs 120 rader
 * *'Private arr() As Integer = {1, 2, 3, 4, 5, 6} ' Ska bli 6! dvs 720 rader
 * *'Private arr() As Integer = {1, 2, 3, 4, 5, 6, 7} ' Ska bli 7! dvs 5040 rader
 * *'Private arr() As Integer = {1, 2, 3, 4, 5, 6, 7, 8} ' Ska bli 8! dvs 40320 rader
 * *'Private arr() As Integer = {1, 2, 3, 4, 5, 6, 7, 8, 9} ' Ska bli 9! dvs drygt 362880 Rader
 * *Private intCounter As Integer

 * *Public Sub start()
 * * * *skriv()
 * * * *Permutera(0)
 * * * *Console.WriteLine("Antal: " & intCounter)

 * *End Sub

 * *Private Sub Permutera(ByVal intStartpos As Integer)
 * * * *Dim intPtr As Integer
 * * * *Dim intSlutPos As Integer
 * * * *Dim intBytPos As Integer
 * * * *intSlutPos = arr.Length - 2
 * * * *intBytPos = arr.Length - 1
 * * * *If intStartpos >= 0 Then
 * * * * * *For intPtr = intStartpos To intSlutPos Step 1
 * * * * * * * *If intStartpos <> intBytPos Then
 * * * * * * * * * *byt(intStartpos, intBytPos)
 * * * * * * * * * *skriv()
 * * * * * * * *End If
 * * * * * * * *Permutera(intStartpos + 1)
 * * * * * *Next
 * * * *End If
 * *End Sub

 * *Private Sub byt(ByVal pos1 As Integer, ByVal pos2 As Integer)
 * * * *Dim posTemp As Integer
 * * * *posTemp = arr(pos1)
 * * * *arr(pos1) = arr(pos2)
 * * * *arr(pos2) = posTemp
 * *End Sub

 * *Private Sub skriv()
 * * * *Dim iPtr As Integer
 * * * *For iPtr = 0 To arr.Length - 1
 * * * * * *Console.Write(arr(iPtr))
 * * * *Next
 * * * *Console.WriteLine()
 * * * *intCounter += 1
 * *End Sub
End Class

[kw_wasabi]

OT: Blir påmind om att jag har kursen "Diskret matematik" som ligger och släpar

[Conny Westh]

Originally posted by kw_wasabi@Mar 13 2009, 03:54
OT: Blir påmind om att jag har kursen "Diskret matematik" som ligger och släpar

Jodå, jag har oxo gått kursen "Diskret matematik" och blev godkänd, men det hjälper inte jag har kört i diket i alla fall...

[eg0master]

I permutera funktionen serjag två saker jag tycker verkar konstiga:

intSlutPos = arr.Length - 2
intBytPos = arr.Length - 1

samt att du inte anväder variablen "intPtr" alls.

[eg0master]

Och nu lite pseudokod för att lösa problemet:

print_array_permutation(array):
  print_array_permutation_helper(array, empty_array)

print_array_permutation_helper(array_in, array_out)
  if array_in.length == 0
    print array_out
  else
    for index = 0 to array_in.length - 1
      object = array_in[index]
      in = array_in.copy()
      in.removeAt(index)
      out = array_out.copy()
      out.append(object)
      print_array_permutation_helper(in, out)

[etanders]

Detta påminner mig om det mycket trevliga språket Haskell, för funktionell programmering. Det blir ofta väldigt kompakt syntax, men har man lärt sig hur det funkar är det otroligt smidigt t.ex. för den här typen av problem.

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

"Kör" man nu perms [1,2,3] blir resultatet
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]