Lottningsprogram

[skogshuggarn]

Tänk er ett lottningsprogram för biltävling
Där antal startnummer kan vara från 4 – 50 eller fler
Fasta värden är alltid 3 omgångar för varje startnummer
I heaten kan det vara 6 st eller 5 st eller 4 st eller 3 st beroende på antal startnummer men högst 6 st i ett heat
Låt säga att det är 15 startnummer o 5 st i varje heat
Första omg är ju lätt
Heat 1. 1,2,3,4,5
Heat 2. 6,7,8,9,10
Heat 3. 11,12,13,14,15
Sen börjar problemen för heat 4 o då omg 2.
Här ska det lottas och samma startnummer får helst inte möta ett samma nummer från om 1
Men det är ju ogörligt med matematiken 15 st 5 i varje heat men samma måste mötas (lotten får avgöra (random) vilken som möts 2 ggr)

Men i 3;e omg så lär det lottas så att inte samma nummer möts 2 ggr då från omg1 och omg 2

Blir det fler än 15 st, uppåt 20-30 st blir det lättare att samma inte kommer i samma heat flera gånger.

Någon som kan göra en algoritm med arrayer o fördela ut heaten i vb för excel
Har skrivit vb-kod med 3,4,5 i heaten men mitt intelekt tar slut
Att skicka upp dem i arrayer för att sortera ut att samma nr inte möts flera gånger
Gör det mauellt vilket är tidskrävande
/tp

[Ove Söderlund]

Detta luktar som ett rätt intressant 'litet' projekt, kan vara relativt enkelt att lösa men ändå väldigt komplext. En tråd på Experts-Exchange.com kan ge en liten hint om vägen framåt en lösning. Koden på sidan är visserligen i VB.net men det är nog inga större problem att lägga om detta i VBA. Jag tror inte att detta är lösbart med enbart kalkylformler.

 

Assigning random values from a fixed pool across 3 "columns" without duplication (experts-exchange.com)

[skogshuggarn]

Detta luktar som ett rätt intressant 'litet' projekt, kan vara relativt enkelt att lösa men ändå väldigt komplext. En tråd på Experts-Exchange.com kan ge en liten hint om vägen framåt en lösning. Koden på sidan är visserligen i VB.net men det är nog inga större problem att lägga om detta i VBA. Jag tror inte att detta är lösbart med enbart kalkylformler.

 

Assigning random values from a fixed pool across 3 "columns" without duplication (experts-exchange.com)

Tack, nä tror inte heller det är lösbart endast genom enbart kalkyl

utan lär nog till lite vba o arryer som jag skrev tidigare, har kommit en bit på väg men kör fast i heat 4 omg 2

[Monshi]

jag funderar på om inte den enklaste lösningen är en form av brute-force.

 

Med det menar jag skapa en ren rak kod som skapar alla möjliga utfall av lottning, eller lämplig delmängd av dem. Poängsätt dem på antal olämpliga möten, dvs där de mötts i tidigare steg och slumpa sedan bland de som får lägst poäng.

Alternativt slumpa hela tiden lottningen och räkna fram poäng på samma sätt för ett resultat av lottningen och godta en lottning om den får mindre än visst antal poäng.

 

Här kan det behövas antingen en skarp hjärna som räknar ut var gränsen för godkänt ska ligga i olika stegen eller annan metod för att skatta ungefär var de bör ligga. Säg tillexempel att möte i första omgångarna (med rak ordning) ger en poäng och möte i senare omgång 5 poäng.. ja du fattar nog vad jag menar på ett ungefär.

 

Och jo, det kan gå att lösa med formler om man bara vill och kanske bara lite kod, kod som bara slumpar fram vilket alternativ som ska användas..

Fast med 50 startnummer blir det ganska långa serier som ska genereras. Å andra sidan har du en gång skapat dem kan du spara dem...

[skogshuggarn]

Har hittat en kod som är nåt liknande som skulle konverterat till vb

http://rubyquiz.com/quiz56.html

 

class Array

  # returns mean of array contents
  def mean
    temp = flatten.compact
    return nil if temp.empty?
    temp.inject { |sum, v| sum + v } / temp.size.to_f
  end

  # returns variance of array contents
  def variance
    temp = flatten.compact
    return nil if temp.empty?
    return 0 if temp.size == 1
    m = temp.mean
    temp.collect {|v| (v - m)**2 }.mean
  end

  # returns std deviation of array contents
  def stddev
    Math.sqrt(variance)
  end

end

# two-dimensional table in which the order of the indices
# doesn't matter. e.g. foo[2,7] is the same cell as foo[7,2].
class Matchups

  def initialize
    @arr = []
  end

  def [](a,
    x, y = a, b
    x, y = y, x if x > y
    @arr[x] && @arr[x][y] || 0
  end

  def []=(a, b, val)
    x, y = a, b
    x, y = y, x if x > y
    @arr[x] ||= []
    @arr[x][y] = val
  end

  # returns a fairly decent representation of the table
  # as long as each element is an integer
  def inspect
    return if @arr.empty?
    w = @arr.compact.collect { |row| row.size }.max
    result = "\n    "
    w.times do |y|
      result += '%3d'%y
    end
    result += "\n"
    @arr.each_index do |x|
      result += '%3d:'%x
      if @arr[x]
        @arr[x].each do |val|
          result += val.nil? ? '   ' : '%3d'%val
        end
      end
      result += "\n"
    end
    result
  end

  # return the table's underlying array
  def to_a
    @arr
  end

end

# internal exception raised when the generator algorithm
# exhausts the available cars to select prematurely
class NoCarsException < RuntimeError
end

# Pinewood Derby chart
class Chart

  attr_reader :lanes, :cars, :rounds, :chart, :devs

  # coefficients for weighting formula for lane assignment.
  # these were derived by experimentation.
  FL = 3.0
  FP = 1.0
  FD = 3.0

  # create a new empty chart with given lanes, cars, and rounds.
  def initialize(lanes, cars, rounds)
    raise "Need at least #{lanes} cars" unless cars >= lanes
    raise "Need at least 1 round" unless rounds >= 1
    @lanes = lanes
    @cars = cars
    @rounds = rounds
    @chart = []
  end

  # create a chart by parsing from a string created by dump
  def self.parse(s)
    a = s.to_a
    lanes = a.shift.to_i
    cars = a.shift.to_i
    rounds = a.shift.to_i
    ch = Chart.new(lanes, cars, rounds)
    a.each do |line|
      ch.chart.push line.split.collect {|x| x.to_i}
    end
    ch.compute_stats
    ch
  end

  # returns dump of chart data
  def dump
    result = ''
    result << "#{lanes}\n"
    result << "#{cars}\n"
    result << "#{rounds}\n"
    chart.each do |heat|
      result << heat.join(' ') << "\n"
    end
    result
  end

  # prints the chart
  def print_chart(io = $stdout)
    io.puts "Chart:"
    h = 0
    chart.each do |heat|
      io.printf "%4d: ", h
      heat.each do |car|
        io.printf "%4d", car
      end
      io.puts
      h += 1
    end
  end

  # compute statistics for current chart
  def compute_stats

    # assigned heats by car
    @ah = Array.new(cars) { 0 }

    # assignments by car/lane
    @al = Array.new(cars) { Array.new(lanes) { 0 } }

    # matchups by car pair
    @op = Matchups.new
    (0...@cars).to_a.each_combination(2) { |x,y| @op[x,y] = 0 if x != y }

    # intervals by car
    lh = Array.new(cars)
    @iv = Array.new(cars) { Array.new }

    # accumulate statistics
    @chart.each_with_index do |h, heat|
      h.each_with_index do |car, lane|
        @ah[car] += 1
        @al[car][lane] += 1
        @iv[car] << heat - lh[car] + 1 if lh[car]
        lh[car] = heat
      end
      h.each_combination(2) {|x,y| @op[x,y] += 1}
    end

    # compute std dev's of each key metric
    @devs = [
      @ah.stddev,             # heats per car
      @al.stddev,             # lanes per car
      @op.to_a.stddev,        # matchups
      @iv.stddev,             # intervals
    ]

  end

  # prints the statistics for the current chart
  def print_stats(io = $stdout)

    raise "No chart has been generated" if @chart.empty?

    io.puts "\nStats:"

    io.puts "\nTotal Heats by Car (Target=#{@lanes * @rounds}):"
    temp = []
    cars.times do |car|
      io.printf "%4d:%4d\n", car, @ah[car]
    end
    io.puts "min=#{@ah.flatten.min}, max=#{@ah.flatten.max}, mean=#{@ah.mean}, stddev=#{@ah.stddev}"

    io.puts "\nLane Assignments by Car (Target=#{@rounds}):"
    io.print '     '
    lanes.times { |lane| io.printf '%4d', lane }
    io.puts
    cars.times do |car|
      io.printf '%4d:', car
      @al[car].each { |count| io.printf '%4d', count }
      io.puts
    end
    io.puts "min=#{@al.flatten.min}, max=#{@al.flatten.max}, mean=#{@al.mean}, stddev=#{@al.stddev}"

    io.print "\nMatchups (Target=#{Float(@lanes) * Float(@lanes - 1) * @rounds / Float(@cars - 1)}):"
    io.print @op.inspect
    io.puts "min=#{@op.to_a.flatten.compact.min}, max=#{@op.to_a.flatten.compact.max}, mean=#{@op.to_a.mean}, stddev=#{@op.to_a.stddev}"

    io.puts "\nIntervals by Car (Target=#{Float(@cars) / @lanes}):"
    temp = []
    @cars.times do |car|
      io.printf '%4d:', car
      @iv[car].each { |interval| io.printf '%4d', interval }
      io.puts
    end
    io.puts "min=#{@iv.flatten.min}, max=#{@iv.flatten.max}, mean=#{@iv.mean}, stddev=#{@iv.stddev}"

  end

end

class ChaoticChart < Chart

  # generates the chart by assigning cars to heats
  def generate

    begin
      # assigned heats by car, last heat by car
      ah = Array.new(cars) { 0 }
      lh = Array.new(cars)

      # assignments by car/lane
      al = Array.new(cars) { Array.new(lanes) { 0 } }

      # matchups by car pair
      op = Matchups.new

      # schedule by heat by lane
      chart.clear

      # generate each heat
      (cars * rounds).times do |heat|

        # current car assignments by lane
        h = []

        # slot each lane
        lanes.times do |lane|

          # computed weights for each car
          w = {}

          # assign weights to each car for this slot
          cars.times do |car|

            # skip car if it's already been slotted to this heat
            next if h.include? car

            # skip car if it's already run max heats in this lane
            next if al[car][lane] >= @rounds

            # weight factor 1: no. of times slotted to this lane
            f1 = FL * al[car][lane]

            # weight factor 2: no. of times against these opponents
            f2 = FP * h.inject(0) do |f, opp|
              f + op[car, opp]
            end

            # weight factor 3: no. of heats since last scheduled
            # (distribute cars through the heats)
            f3 = 0
            if lh[car]
              f3 = FD * (cars / lanes) / (heat - lh[car])
            end

            # total weight for this car
            w[car] = f1 + f2 + f3

          end

          raise NoCarsException if w.empty?

          # sort by weight and get the lowest weight(s)
          w = w.sort_by { |k, v| v }
          w.pop while w[-1][1] > w[0][1]

          # randomly choose a car and slot it
          car = w[rand(w.size)][0]

          # accumulate statistics
          ah[car] += 1
          lh[car] = heat
          al[car][lane] += 1
          h.each do |opp|
            op[car, opp] += 1
          end

          # slot car to current heat
          h << car

        end

        # add current heat to chart
        chart << h

      end

    rescue NoCarsException
      retry

    end

  end

end

class RoundRobinChart < Chart

  # generate chart via simple round-robin assignment
  def generate
    chart.clear
    car = 0
    (cars * rounds).times do |heat|
      h = []
      lanes.times do
        h << car
        car = (car + 1) % cars
      end
      chart << h
    end
  end

end

if $0 == __FILE__

  if (ARGV.size < 3)
    puts "Usage: #$0 lanes cars rounds [class]"
    puts "       (constraints: lanes > 1, cars >= lanes, rounds >= 1)"
    exit
  end
  klass = 'ChaoticChart'
  klass = ARGV.pop if ARGV.size == 4
  c = Object.const_get(klass).new(*ARGV.collect {|v| v.to_i}) rescue begin
    $stderr.puts $!
    exit
  end
  c.generate
  c.print_chart
  c.compute_stats
  c.print_stats

end
 

[Gäst]

du beskriver det rätt bra, och då behövs bara implementation på den logiken. Sedan använder du annat än arrayer. Du finns ju andra typer av datastrukturer som redan innehåller logik för det du beskriver...

[Ove Söderlund]

Om man är beredd på att kavla upp ärmarna och jobba lite så finns det redan ett Excel-program (add-in till Excel för att vara mer exakt) som kan utföra det TS önskar, Pinewood ExcelDerby, och du hittar det längst ner på denna sida samt manual:

Many Waters District Pinewood Derby (Many Water Districts / .org)

 

Några cons att ta hänsyn till:

- Installationsprogrammet fungerar inte i 64-bits miljö.

- Gammalt program från 2003/04-ish vilket gjorde att mitt Excel 2010 protesterade med hänvisning till "osäkert program" pga saknade certifikat el.dyl.

- Omfattande kod som kan behöva en rejäl genomgång för att kunna bli kompatibel med nyare Excel-versioner.

 

Å andra sidan.... får du detta att fungera så har du en mjukvara som kommer att vara väldigt flexibel.

[skogshuggarn]

jag funderar på om inte den enklaste lösningen är en form av brute-force.

 

Med det menar jag skapa en ren rak kod som skapar alla möjliga utfall av lottning, eller lämplig delmängd av dem. Poängsätt dem på antal olämpliga möten, dvs där de mötts i tidigare steg och slumpa sedan bland de som får lägst poäng.

Alternativt slumpa hela tiden lottningen och räkna fram poäng på samma sätt för ett resultat av lottningen och godta en lottning om den får mindre än visst antal poäng.

 

Här kan det behövas antingen en skarp hjärna som räknar ut var gränsen för godkänt ska ligga i olika stegen eller annan metod för att skatta ungefär var de bör ligga. Säg tillexempel att möte i första omgångarna (med rak ordning) ger en poäng och möte i senare omgång 5 poäng.. ja du fattar nog vad jag menar på ett ungefär.

 

Och jo, det kan gå att lösa med formler om man bara vill och kanske bara lite kod, kod som bara slumpar fram vilket alternativ som ska användas..

Fast med 50 startnummer blir det ganska långa serier som ska genereras. Å andra sidan har du en gång skapat dem kan du spara dem...

Hur har du tänkt

[skogshuggarn]

Nja bättre å få en lösning på min första fråga

[Monshi]

Hur har du tänkt

Inte mycket mer än jag skrivit ovan. Att grovt bygga upp alla möjliga utfall, poängsätta dem smart och singla ut de som får bäst poäng.

med tre lag ganska enkelt med 25 ganska många alternativ...