Coder needed

[lavezzi]

Hello.

I need some1 to code this function for me.

Please write down your bid and release time.

What the function should do (example):

Given X boxes and Y coins it should tell me each of the possibile combination.

For 3 Boxes and 4 coins the result is only 1 and should be:

211

For 3 Boxes and 5 coins the result should be:

311

221

Obviously the function should be dynamic so the number of coins or boxes may be any number.

The function need to accept as params X and Y as explained above. X and Y are numbers.

I dont need the number of combination, i need each result.

For each possible distribution I need its permutation.

so 211 will also be:

121

112

This function is not so easy if we take in account as boxes 2000 and coins 100.000, dont be fooled!

Other than paying the coder Ill do a small donation to autoit!!

Edited June 16, 2009 by lavezzi

[PsaltyDS]

Hello.

I need some1 to code this function for me.

Please write down your bid and release time.

What the function should do (example):

Given X boxes and Y coins it should tell me each of the possibile combination.

For 3 Boxes and 4 coins the result is only 1 and should be:

211

For 3 Boxes and 5 coins the result should be:

311

221

Obviously the function should be dynamic so the number of coins or boxes may be any number.

The function need to accept as params X and Y as explained above. X and Y are numbers.

I dont need the number of combination, i need each result.

For each possible distribution I need its permutation.

so 211 will also be:

121

112

This function is not so easy if we take in account as boxes 2000 and coins 100.000, dont be fooled!

Other than paying the coder Ill do a small donation to autoit!!

That's a well known puzzle problem, and often assigned for various classes in math or computer science. Your statement of the problem already makes assumptions not explicitly given, like no box can have 0, and boxes have no identity (so 3/1/1 and 1/3/1 are not different results).

Is this your homework?

[PcExpert]

[offtopic]@PsaltyDS,

If it is his homework, do you think that he will answer 'yes' to your question? [/offtopic]

Edited June 16, 2009 by PcExpert

[zorphnog]

I was thinking the same thing. What's the point in taking a class if you don't even want to learn.

[PcExpert]

By the way, do you really have to ask this twice? First topic THe aswer to your question is also already in that topic.

Edited June 16, 2009 by PcExpert

[lavezzi]

That's a well known puzzle problem, and often assigned for various classes in math or computer science. Your statement of the problem already makes assumptions not explicitly given, like no box can have 0, and boxes have no identity (so 3/1/1 and 1/3/1 are not different results).

Is this your homework?

That's the smarter reply I've received. Both the assumptions are extremely right, but:

the first can be solved easly because I can pass to the function the total number of coins less the number of boxes so I will get no boxes with zero value.

the second is also correct. I've already found a permutation functions but it works only with a string containing a single digit char where i need bigger number (3 dgt).

To your question I have to reply no, this is not my homework.

By the way, do you really have to ask this twice? First topic THe aswer to your question is also already in that topic.

Well I've found two ppl that wanted to code this, 1 never replied via PM and the oher had some problem.

So yes, I needed at least to try this twice.

That permutations functions seems not to permute something like 12,222,33, I will investigate, but it does not seems to give me unique distribution.

I will not ask with any other thread. I will ask elsewhere and try to study this:

http://en.wikipedia.org/wiki/Permutation

http://en.wikipedia.org/wiki/Recursion_(computer_science)

http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm

[lavezzi]

easy solution for distribution problem:

http://en.wikipedia.org/wiki/Category:Cont...s_distributions

[martin]

easy solution for distribution problem:

http://en.wikipedia.org/wiki/Category:Cont...s_distributions

Have you arranged to pay anyone for this?

[lavezzi]

Have you arranged to pay anyone for this?

Martin no one accepted and delivered the work.

I'm doing it by myself.

Actually the following code does not work (im working on it right now), but I should be near to the solution.

expandcollapse popup

$string="4,0,0,0"
;~ $a=issplittable("3,1,1")

;~ split($string)
distrib(5,3)
Exit

func distrib($coins,$boxes)
;~  GENERATE ARRAY
    local $p[$boxes+1]
    local $x=$boxes
    local $msg
    local $mysequence
    $p[1]=$coins-$boxes+1
    while $x>1
        $p[$x]=1
        $x=$x-1
    wend
    $y=1
    while $y<=$boxes
        $mysequence=$mysequence & $p[$y] & ","
        $y=$y+1
    wend
    
    $mysequence=StringTrimRight($mysequence,1) 
    
    while $p[1]>0
        $a= issplittable($mysequence)
        MsgBox("","is splittable:",$a & "(" & $mysequence & ")")
        $activeElement=1
        while $activeElement<$boxes
            while issplittable($mysequence)=1
                
                $mysequence=split($mysequence)
                MsgBox("","After Split",$mysequence)
            wend
            $activeElement=$activeElement+1
        wend
        $p[1]=$p[1]-1
        $p[2]=$p[2]+1
    wend
MsgBox("","END","THE END")
EndFunc


func split($string)
    $elements=StringSplit($string,",",1)
    $arrayCount=Ubound($elements)   
    $elements[1]=$elements[1]-1
    $elements[2]=$elements[2]+1 
    $x=1
    $string=""
    while $x<$arrayCount
        $string=$string & $elements[$x] & ","
        $x=$x+1
    wend
    $string=StringTrimRight($string,1) 
    return $string
EndFunc

func issplittable($string)
    $elements=StringSplit($string,",",1)
    $arrayCount=Ubound($elements) 
;~  MsgBox("","count",$arrayCount)
    if $arrayCount-1>2 then     
        if ($elements[1]>$elements[2] AND $elements[1]+1>$elements[2])   Then
        
            return 1
        EndIf
    else
        if ($elements[1]+1>$elements[2]) then
            return 1
        Else
            return 0
        EndIf
    endif
EndFunc

PS:I've given an user 10$, if he will return them to me I will donate them to Autoit

Edited June 16, 2009 by lavezzi

[martin]

Martin no one accepted and delivered the work.

I'm doing it by myself.

Actually the following code does not work (im working on it right now), but I should be near to the solution.

expandcollapse popup

$string="4,0,0,0"
;~ $a=issplittable("3,1,1")
  
;~ split($string)
  distrib(5,3)
  Exit
  
  func distrib($coins,$boxes)
;~   GENERATE ARRAY
      local $p[$boxes+1]
      local $x=$boxes
      local $msg
      local $mysequence
      $p[1]=$coins-$boxes+1
      while $x>1
          $p[$x]=1
          $x=$x-1
      wend
      $y=1
      while $y<=$boxes
          $mysequence=$mysequence & $p[$y] & ","
          $y=$y+1
      wend
      
      $mysequence=StringTrimRight($mysequence,1) 
      
      while $p[1]>0
          $a= issplittable($mysequence)
          MsgBox("","is splittable:",$a & "(" & $mysequence & ")")
          $activeElement=1
          while $activeElement<$boxes
              while issplittable($mysequence)=1
                  
                  $mysequence=split($mysequence)
                  MsgBox("","After Split",$mysequence)
              wend
              $activeElement=$activeElement+1
          wend
          $p[1]=$p[1]-1
          $p[2]=$p[2]+1
      wend
  MsgBox("","END","THE END")
  EndFunc
  
  
  func split($string)
      $elements=StringSplit($string,",",1)
      $arrayCount=Ubound($elements)  
      $elements[1]=$elements[1]-1
      $elements[2]=$elements[2]+1   
      $x=1
      $string=""
      while $x<$arrayCount
          $string=$string & $elements[$x] & ","
          $x=$x+1
      wend
      $string=StringTrimRight($string,1) 
      return $string
  EndFunc
  
  func issplittable($string)
      $elements=StringSplit($string,",",1)
      $arrayCount=Ubound($elements) 
;~   MsgBox("","count",$arrayCount)
      if $arrayCount-1>2 then       
          if ($elements[1]>$elements[2] AND $elements[1]+1>$elements[2])   Then
          
              return 1
          EndIf
      else
          if ($elements[1]+1>$elements[2]) then
              return 1
          Else
              return 0
          EndIf
      endif
  EndFunc

PS:I've given an user 10$, if he will return them to me I will donate them to Autoit

OK, well if you think this works maybe you can donate the money to AutoIt anyway.

Dim $b[5];5 boxes
ConsoleWrite(distr(8) & @CRLF);distribute 20 coins with at least one coin in each box

Func distr($c, $t = 1)
    If $t = 1 Then;first box?
        If $c < UBound($b) Then Return -1
        $c -= UBound($b)
    EndIf
    
    If $c = 0 Then;no coins left?
        For $n = $t To UBound($b)
            $b[$n - 1] = 1
        Next
        Return Res()
    EndIf
    
    If $t = UBound($b)  Then;last box?
        $b[$t - 1] = $c + 1
        Return Res()
    EndIf
    
    For $n = 0 To $c ;for each coin left
        $b[$t - 1] = $n + 1
        distr($c - $n, $t + 1)
    Next
    Return
EndFunc  ;==>distr

Func Res()
    Local $r = ''
    For $j = 0 To UBound($b) - 1
        $r &= $b[$j] & ', '
    Next
    ConsoleWrite($r & @CRLF)
EndFunc  ;==>Res

EDIT: I didn't work as I thought so I've changed it.

Edited June 16, 2009 by martin

[lavezzi]

OK, well if you think this works maybe you can donate the money to AutoIt anyway.

Dim $b[5];5 boxes
ConsoleWrite(distr(8) & @CRLF);distribute 20 coins with at least one coin in each box

Func distr($c, $t = 1)
    If $t = 1 Then;first box?
        If $c < UBound($b) Then Return -1
        $c -= UBound($b)
    EndIf
    
    If $c = 0 Then;no coins left?
        For $n = $t To UBound($b)
            $b[$n - 1] = 1
        Next
        Return Res()
    EndIf
    
    If $t = UBound($b)  Then;last box?
        $b[$t - 1] = $c + 1
        Return Res()
    EndIf
    
    For $n = 0 To $c;for each coin left
        $b[$t - 1] = $n + 1
        distr($c - $n, $t + 1)
    Next
    Return
EndFunc ;==>distr

Func Res()
    Local $r = ''
    For $j = 0 To UBound($b) - 1
        $r &= $b[$j] & ', '
    Next
    ConsoleWrite($r & @CRLF)
EndFunc ;==>Res

EDIT: I didn't work as I thought so I've changed it.

need to test it (im at work), but yes, I will donate!

[Juvigy]

I am working on the issue but i have severe speed issues with larger numbers:

"distribute 20 coins with at least one coin in each box" - this is only a test - it should work with any number of coins and boxes. Right?

The 20 coins and 5 boxes has 3200000 solutions. If order is not important = 42504 . If repetition is not allowed =15504 . Imagine what happens with larger numbers.

[martin]

I am working on the issue but i have severe speed issues with larger numbers:

"distribute 20 coins with at least one coin in each box" - this is only a test - it should work with any number of coins and boxes. Right?

The 20 coins and 5 boxes has 3200000 solutions. If order is not important = 42504 . If repetition is not allowed =15504 . Imagine what happens with larger numbers.

The numbers are not that large.

20 coins in 5 boxes where there is at least 1 coin in each box gives 3,876 possible combinations where

16,1,1,1,1 is not the same as

1,16,1,1,1

40 coins in 5 boxes gives 82,251 possible solutions.

If the time is a problem you need to write the script in a language which can be compiled.

Using AutoIt on a very average PC, 25 coins in 10 boxes took 37.6 seconds to produce 1,307,504 combinations. The same program in Delphi took less than 2 seconds.

[Juvigy]

You are right as i am calculating without Considering that 17,18,19,20 cant be used (due to the fact there should be at least on coin). What approach do you use?

The max values that will be used are 180 coins and 9 boxes.

Edited June 18, 2009 by Juvigy

[martin]

You are right as i am calculating without Considering that 17,18,19,20 cant be used (due to the fact there should be at least on coin). What approach do you use?

The max values that will be used are 180 coins and 9 boxes.

I don't understand what you mean by "what approach do you use?". I used the edited code I posted, but for the the time test I just replaced the res function with

Func Res()
  $INumResults += 1;where $iNimResults was a global variable set to 0 at the start.
EndFunc

.

Or did you mean something else?

I'll try 180 coins in 9 boxes in the Delphi version and let you klnow how long it takes. (Assuming it doesn't take more than a couple of hours!)

There is probably a more efficient way to solve the problem.

[martin]

I don't understand what you mean by "what approach do you use?". I used the edited code I posted, but for the the time test I just replaced the res function with

Func Res()
   $INumResults += 1;where $iNimResults was a global variable set to 0 at the start.
 EndFunc

.

Or did you mean something else?

I'll try 180 coins in 9 boxes in the Delphi version and let you klnow how long it takes. (Assuming it doesn't take more than a couple of hours!)

There is probably a more efficient way to solve the problem.

I ran the Delphi version and stopped it after it had been running for about 47000 seconds and had found over 1,500,000,000,000 possibilities. It was nowhere near to finishing.

[kjcdude]

I'm so lost as to why anyone would want to write something like this for any reason beyond school work.

[martin]

I'm so lost as to why anyone would want to write something like this for any reason beyond school work.

I'm unable to see why anyone would want to post a message like that. Surely you've got something better to do with your time.