Искусство программирования (задача 7)

[Alder]

Разомнем немного мозги

Дана таблица вида:

Код:

    | a | b | c |
  1 |   |   |   |
  2 |   |   |   |
  . |   |   |   |
  . |   |   |   |
  n |   |   |   |

В ячейках произвольно расставлены галочки, минимум одна галочка в строке, например

Код:

    | a | b | c |
  1 |   | v |   |
  2 | v |   | v |
  3 |   |   | v |
  4 | v |   |   |
  5 | v |   |   |

Нужно вычислить все варианты различных комбинаций галочек от первой до последней строки(a, b и c). То есть для примера выше ответ такой:
Два варианта.
Вариант 1: bacaa
Вариант 2: bccaa

Побеждает минимальная по объему программа. Языки реализации - любые (у меня есть ответ на Ruby, он меня поразил своей краткостью)

[Sochin]

Код: (C# 3.0)

   static class Program
    {
        static IEnumerable<string> Combinations(this IEnumerable<string> table)
        {
            foreach (var result in
                from line in table.Count() > 1 ? table.Take(table.Count() - 1).Combinations() : new string[] { string.Empty }
                from character in table.Count() > 0 ? table.Last() : string.Empty
                select line + character)
                yield return result;
        }

        static void Main(string[] args)
        {
            foreach (string s in new string[] { "B", "AC", "C", "A", "A" }.Combinations())
                Console.WriteLine(s);
        }
    }

[Alder]

А кроме Сочина больше никому не интересно?

[LazarusLong]

А кроме Сочина больше никому не интересно?

Я не совсем врублюсь в условие, а так бы поучаствовал.

[Sochin]

Код: ("F#")

#light
printf "%A" (["B"; "AС"; "С"; "A"; "A"] 
|> Seq.fold (fun result current -> [for c in current do for s in result -> s + (string)c]) [""])

["BAСAA"; "BССAA"]

Алдер, давай свой вариант. =)

[Alder]

Код: ("Ruby")

# Produces list of permutations of elements according to a set of rules.
#
# Rules determine which elements are acceptable in each position of a single
# permutation. First rule determines which elements are acceptable in the first
# position of a permutation, second rule -- to a second position, and so on.

def permutations(rules)
  rules.inject([[]]) { |solution, rule| apply_rule(solution, rule) }
end

# extends each element of solution with each element of a rule
def apply_rule(solution, rule) 
  rule.inject([]) do |acc, possible_value|
    acc.concat(append(possible_value, solution))
  end
end
# returns an array produced by prepending a +value+ to each element of
# +permutations+.
def append(value, permutations)
  permutations.map { |p| p.dup.push(value) }
end

RULES = [[   :x,   2],
   [   :x,    ],
   [1,   :x,  2],
   [   :x,    ]];

puts permutations(RULES).map {|p| p.inspect}.join("\n")

Думаю, что код Сочина на F# будет самым коротким

[Storm]

F# не знаю, ничего не скажу, но, ИМХО, подобного плана задачи следует решать с применением лишь условного ветвления и цикла с заданным количеством итераций, как учил Дейкстра, иначе это все будет сведено к мерянью языками программирования.

можно написать модуль для Perl с реализацией поставленной задачи и программа будет  сведена к вызову функции с возвратом ссылки на список.

да и задачу уточнить не помешает, потому что не въехал какие варианты на выходе должны быть.

[Sochin]

F# не знаю, ничего не скажу, но, ИМХО, подобного плана задачи следует решать с применением лишь условного ветвления и цикла с заданным количеством итераций, как учил Дейкстра, иначе это все будет сведено к мерянью языками программирования.

Мир не замкнут на одних лишь императивных языках. Так что если и мерянье, то скорее парадигмами. =)