language-agnostic - XKCD で NP 完全問題を解く

Question

問題/問題のコミック: http://xkcd.com/287/

これが最善の方法かどうかはわかりませんが、これまでのところ私が思いついた方法は次のとおりです。私は CFML を使用していますが、誰でも読めるはずです。

<cffunction name="testCombo" returntype="boolean">
    <cfargument name="currentCombo" type="string" required="true" />
    <cfargument name="currentTotal" type="numeric" required="true" />
    <cfargument name="apps" type="array" required="true" />

    <cfset var a = 0 />
    <cfset var found = false />

    <cfloop from="1" to="#arrayLen(arguments.apps)#" index="a">
        <cfset arguments.currentCombo = listAppend(arguments.currentCombo, arguments.apps[a].name) />
        <cfset arguments.currentTotal = arguments.currentTotal + arguments.apps[a].cost />
        <cfif arguments.currentTotal eq 15.05>
            <!--- print current combo --->
            <cfoutput><strong>#arguments.currentCombo# = 15.05</strong></cfoutput><br />
            <cfreturn true />
        <cfelseif arguments.currentTotal gt 15.05>
            <cfoutput>#arguments.currentCombo# > 15.05 (aborting)</cfoutput><br />
            <cfreturn false />
        <cfelse>
            <!--- less than 15.05 --->
            <cfoutput>#arguments.currentCombo# < 15.05 (traversing)</cfoutput><br />
            <cfset found = testCombo(arguments.currentCombo, arguments.currentTotal, arguments.apps) />
        </cfif>
    </cfloop>
</cffunction>

<cfset mf = {name="Mixed Fruit", cost=2.15} />
<cfset ff = {name="French Fries", cost=2.75} />
<cfset ss = {name="side salad", cost=3.35} />
<cfset hw = {name="hot wings", cost=3.55} />
<cfset ms = {name="moz sticks", cost=4.20} />
<cfset sp = {name="sampler plate", cost=5.80} />
<cfset apps = [ mf, ff, ss, hw, ms, sp ] />

<cfloop from="1" to="6" index="b">
    <cfoutput>#testCombo(apps[b].name, apps[b].cost, apps)#</cfoutput>
</cfloop>

上記のコードは、$15.05 になる唯一の組み合わせはミックス フルーツの 7 注文であり、完了するまでに testCombo 関数を 232 回実行する必要があることを示しています。

正しい解決策に到達するためのより良いアルゴリズムはありますか? 私は正しい解決策にたどり着きましたか？

Answer 1

それはソリューションのすべての順列を提供しますが、私はコードサイズで他の誰よりも優れていると思います.

item(X) :- member(X,[215, 275, 335, 355, 420, 580]).
solution([X|Y], Z) :- item(X), plus(S, X, Z), Z >= 0, solution(Y, S).
solution([], 0).

swiprolog を使用したソリューション:

?- solution(X, 1505).

X = [215, 215, 215, 215, 215, 215, 215] ;

X = [215, 355, 355, 580] ;

X = [215, 355, 580, 355] ;

X = [215, 580, 355, 355] ;

X = [355, 215, 355, 580] ;

X = [355, 215, 580, 355] ;

X = [355, 355, 215, 580] ;

X = [355, 355, 580, 215] ;

X = [355, 580, 215, 355] ;

X = [355, 580, 355, 215] ;

X = [580, 215, 355, 355] ;

X = [580, 355, 215, 355] ;

X = [580, 355, 355, 215] ;

No

Answer 2

NP 完全問題のポイントは、小さなデータセットでは難しいということではなく、それを解く作業量が多項式よりも速い速度で増加するということです。つまり、O(n^x) アルゴリズムがないということです。

上記の2つの問題のように、時間の複雑さがO（n！）の場合、それはNPにあります。

Answer 3

(Perl の場合) 再帰を使った方がエレガントではないですか?

#!/usr/bin/perl
use strict;
use warnings;

my @weights  = (2.15, 2.75, 3.35, 3.55, 4.20, 5.80);

my $total = 0;
my @order = ();

iterate($total, @order);

sub iterate
{
    my ($total, @order) = @_;
    foreach my $w (@weights)
    {
        if ($total+$w == 15.05)
        {
            print join (', ', (@order, $w)), "\n";
        }
        if ($total+$w < 15.05)
        {
            iterate($total+$w, (@order, $w));
        }
    }
}

出力

marco@unimatrix-01:~$ ./xkcd-knapsack.pl
2.15, 2.15, 2.15, 2.15, 2.15, 2.15, 2.15
2.15, 3.55, 3.55, 5.8
2.15, 3.55, 5.8, 3.55
2.15, 5.8, 3.55, 3.55
3.55, 2.15, 3.55, 5.8
3.55, 2.15, 5.8, 3.55
3.55, 3.55, 2.15, 5.8
3.55, 5.8, 2.15, 3.55
5.8, 2.15, 3.55, 3.55
5.8, 3.55, 2.15, 3.55

Answer 4

ナップサックはNP完全ですが、それは非常に特別な問題です。通常の動的プログラムは実際には優れています（http://en.wikipedia.org/wiki/Knapsack_problem）

そして、正しい分析を行うと、それはO（nW）であり、nはアイテムの数であり、Wはターゲット数であることがわかります。問題は、大きなWでDPを実行する必要がある場合、つまりNPの動作を取得する場合です。しかし、ほとんどの場合、ナップザックは適度に適切に動作し、問題なくその非常に大きなインスタンスを解決できます。NP完全問題に関する限り、ナップザックは最も簡単な問題の1つです。

Answer 5

これがconstraint.pyを使用したソリューションです

>>> from constraint import *
>>> problem = Problem()
>>> menu = {'mixed-fruit': 2.15,
...  'french-fries': 2.75,
...  'side-salad': 3.35,
...  'hot-wings': 3.55,
...  'mozarella-sticks': 4.20,
...  'sampler-plate': 5.80}
>>> for appetizer in menu:
...    problem.addVariable( appetizer, [ menu[appetizer] * i for i in range( 8 )] )
>>> problem.addConstraint(ExactSumConstraint(15.05))
>>> problem.getSolutions()
[{'side-salad': 0.0, 'french-fries': 0.0, 'sampler-plate': 5.7999999999999998, 'mixed-fruit': 2.1499999999999999, 'mozarella-sticks': 0.0, 'hot-wings': 7.0999999999999996},
 {'side-salad': 0.0, 'french-fries': 0.0, 'sampler-plate': 0.0, 'mixed-fruit':     15.049999999999999, 'mozarella-sticks': 0.0, 'hot-wings': 0.0}]

したがって、解決策は、サンプラー プレート、ミックス フルーツ、および 2 つのホット ウイングを注文するか、7 つのミックス フルーツを注文することです。

Answer 6

F# を使用したソリューションは次のとおりです。

#light

type Appetizer = { name : string; cost : int }

let menu = [
    {name="fruit"; cost=215}
    {name="fries"; cost=275}
    {name="salad"; cost=335}
    {name="wings"; cost=355}
    {name="moz sticks"; cost=420}
    {name="sampler"; cost=580}
    ] 

// Choose: list<Appetizer> -> list<Appetizer> -> int -> list<list<Appetizer>>
let rec Choose allowedMenu pickedSoFar remainingMoney =
    if remainingMoney = 0 then
        // solved it, return this solution
        [ pickedSoFar ]
    else
        // there's more to spend
        [match allowedMenu with
         | [] -> yield! []  // no more items to choose, no solutions this branch
         | item :: rest -> 
            if item.cost <= remainingMoney then
                // if first allowed is within budget, pick it and recurse
                yield! Choose allowedMenu (item :: pickedSoFar) (remainingMoney - item.cost)
            // regardless, also skip ever picking more of that first item and recurse
            yield! Choose rest pickedSoFar remainingMoney]

let solutions = Choose menu [] 1505

printfn "%d solutions:" solutions.Length 
solutions |> List.iter (fun solution ->
    solution |> List.iter (fun item -> printf "%s, " item.name)
    printfn ""
)

(*
2 solutions:
fruit, fruit, fruit, fruit, fruit, fruit, fruit,
sampler, wings, wings, fruit,
*)

Answer 7

アルゴリズム自体の設計について1つの提案をします（これは、元の質問の意図をどのように解釈したかです）。ここに私が書いた解決策の断片があります：

....

private void findAndReportSolutions(
    int target,  // goal to be achieved
    int balance, // amount of goal remaining
    int index    // menu item to try next
) {
    ++calls;
    if (balance == 0) {
        reportSolution(target);
        return; // no addition to perfect order is possible
    }
    if (index == items.length) {
        ++falls;
        return; // ran out of menu items without finding solution
    }
    final int price = items[index].price;
    if (balance < price) {
        return; // all remaining items cost too much
    }
    int maxCount = balance / price; // max uses for this item
    for (int n = maxCount; 0 <= n; --n) { // loop for this item, recur for others
        ++loops;
        counts[index] = n;
        findAndReportSolutions(
            target, balance - n * price, index + 1
        );
    }
}

public void reportSolutionsFor(int target) {
    counts = new int[items.length];
    calls = loops = falls = 0;
    findAndReportSolutions(target, target, 0);
    ps.printf("%d calls, %d loops, %d falls%n", calls, loops, falls);
}

public static void main(String[] args) {
    MenuItem[] items = {
        new MenuItem("mixed fruit",       215),
        new MenuItem("french fries",      275),
        new MenuItem("side salad",        335),
        new MenuItem("hot wings",         355),
        new MenuItem("mozzarella sticks", 420),
        new MenuItem("sampler plate",     580),
    };
    Solver solver = new Solver(items);
    solver.reportSolutionsFor(1505);
}

...

(残りのメニュー項目よりも残りの残高が少ない場合に一定時間の早期終了を有効にするために、コンストラクターは価格の昇順でメニュー項目を並べ替えることに注意してください。)

サンプル実行の出力は次のとおりです。

7 mixed fruit (1505) = 1505
1 mixed fruit (215) + 2 hot wings (710) + 1 sampler plate (580) = 1505
348 calls, 347 loops, 79 falls

強調したい設計上の提案は、上記のコードで、ネストされた (再帰的な) 呼び出しのそれぞれが、引数findAndReportSolution(...)によって識別される 1 つのメニュー項目の数量を処理することです。indexつまり、再帰的な入れ子は、入れ子になったループのインライン セットの動作に似ています。最も外側のカウントは最初のメニュー項目の可能な使用をカウントし、次のインは 2 番目のメニュー項目の使用をカウントします (もちろん、再帰を使用すると、特定の数のメニュー項目への依存からコードが解放されます!)

これにより、コードの設計が容易になり、各呼び出しが何を行っているかを理解しやすくなることをお勧めします (特定のアイテムのすべての可能な用途を考慮し、メニューの残りの部分を下位の呼び出しに委譲します)。また、複数アイテムのソリューションのすべての配置を生成する組み合わせの爆発を回避します (上記の出力の 2 行目のように、アイテムの異なる順序で繰り返し発生するのではなく、1 回だけ発生します)。

特定のメソッドの呼び出し回数を最小限に抑えようとするのではなく、コードの「自明性」を最大限に高めようとします。たとえば、上記の設計では、委任された呼び出しで解決策に達したかどうかを判断できます。呼び出しのポイントにそのチェックをラップするのではなく、コードが乱雑になることを犠牲にして呼び出しの数を減らします。

Answer 8

これですべての正しい組み合わせが得られましたが、まだ必要以上に多くのことをチェックしています (結果が示す多くの順列からも明らかなように)。また、15.05 マークに到達する最後の項目を省略しています。

再帰呼び出しを 209 回繰り返す PHP バージョンがあります (すべての順列を取得すると 2012 年になります)。ループの終了直前に、チェックしたアイテムを引き出すと、カウントを減らすことができます。

CF構文はわかりませんが、次のようになります。

        <cfelse>
            <!--- less than 15.50 --->
            <!--<cfoutput>#arguments.currentCombo# < 15.05 (traversing)</cfoutput><br />-->
            <cfset found = testCombo(CC, CT, arguments.apps) />
        ------- remove the item from the apps array that was just checked here ------
    </cfif>
</cfloop>

編集:参考までに、ここに私のPHPバージョンがあります:

<?
  function rc($total, $string, $m) {
    global $c;

    $m2 = $m;
    $c++;

    foreach($m as $i=>$p) {
      if ($total-$p == 0) {
        print "$string $i\n";
        return;
      }
      if ($total-$p > 0) {
        rc($total-$p, $string . " " . $i, $m2);
      }
      unset($m2[$i]);
    }
  }

  $c = 0;

  $m = array("mf"=>215, "ff"=>275, "ss"=>335, "hw"=>355, "ms"=>420, "sp"=>580);
  rc(1505, "", $m);
  print $c;
?>

出力

 mf mf mf mf mf mf mf
 mf hw hw sp
209

編集2：

要素を削除できる理由を説明するには、コメントに収まりきらないほど時間がかかるため、ここに追加します。

基本的に、各再帰は、現在の検索要素を含むすべての組み合わせを検索します (たとえば、最初のステップでは、少なくとも 1 つの混合果物を含むすべてを検索します)。一番分かりやすいのは実行をトレースすることですが、それはかなりのスペースを必要とするので、ターゲットが 6.45 であるかのように実行します。

MF (2.15)
  MF (4.30)
    MF (6.45) *
    FF (7.05) X
    SS (7.65) X
    ...
  [MF removed for depth 2]
  FF (4.90)
    [checking MF now would be redundant since we checked MF/MF/FF previously]
    FF (7.65) X
    ...
  [FF removed for depth 2]
  SS (5.50)
  ...
[MF removed for depth 1]

この時点で、ミックス フルーツを含むすべての組み合わせをチェックしたので、ミックス フルーツを再度チェックする必要はありません。同じロジックを使用して、より深い再帰のそれぞれで配列を整理することもできます。

このようにトレースすると、実際には別のわずかな時間節約が示唆されました.価格が低いものから高いものに分類されていることを知っているということは、目標を超えたらアイテムをチェックし続ける必要がないことを意味します.

Answer 9

ナップザック問題を読んでください。

Answer 10

うーん、あなたは何がおかしいのか知っています。解決策は、メニューの最初の項目の7つです。

これは明らかに短期間で紙と鉛筆で解決することを意図していたので、注文の合計を各アイテムの価格で割って、万が一1つのアイテムの倍数を注文したかどうかを確認してみませんか？

例えば、

15.05 / 2.15=7つのミックスフルーツ15.05/2.75=5.5フライドポテト。

そして、単純な組み合わせに移ります...

15 /（2.15 + 2.75）=3.06122449フライドポテトとミックスフルーツ。

言い換えれば、解決策は、コンピューターにアクセスすることなく、人間によって単純で解決可能であると想定されていると仮定します。次に、最も単純で最も明白な（したがって、目に見えない）ソリューションが機能するかどうかをテストします。

クラブが閉店した後の午前4時30分に4.77ドル相当の前菜（税込）を注文した今週末、地元のコニーでこれを引っ張っていることを誓います。

Answer 11

パイソンで。
「グローバル変数」に問題があったため、関数をオブジェクトのメソッドとして配置しました。それは再帰的であり、漫画の質問に対して 29 回自分自身を呼び出し、最初に成功した一致で停止します。

class Solver(object):
    def __init__(self):
        self.solved = False
        self.total = 0
    def solve(s, p, pl, curList = []):
        poss = [i for i in sorted(pl, reverse = True) if i <= p]
        if len(poss) == 0 or s.solved:
            s.total += 1
            return curList
        if abs(poss[0]-p) < 0.00001:
            s.solved = True # Solved it!!!
            s.total += 1
            return curList + [poss[0]]
        ml,md = [], 10**8
        for j in [s.solve(p-i, pl, [i]) for i in poss]:
            if abs(sum(j)-p)<md: ml,md = j, abs(sum(j)-p)
        s.total += 1
        return ml + curList


priceList = [5.8, 4.2, 3.55, 3.35, 2.75, 2.15]
appetizers = ['Sampler Plate', 'Mozzarella Sticks', \
              'Hot wings', 'Side salad', 'French Fries', 'Mixed Fruit']

menu = zip(priceList, appetizers)

sol = Solver()
q = sol.solve(15.05, priceList)
print 'Total time it runned: ', sol.total
print '-'*30
order = [(m, q.count(m[0])) for m in menu if m[0] in q]
for o in order:
    print '%d x %s \t\t\t (%.2f)' % (o[1],o[0][1],o[0][0])

print '-'*30
ts = 'Total: %.2f' % sum(q)
print ' '*(30-len(ts)-1),ts

出力：

Total time it runned:  29
------------------------------
1 x Sampler Plate   (5.80)
2 x Hot wings       (3.55)
1 x Mixed Fruit       (2.15)
------------------------------
               Total: 15.05

Answer 12

最適化されたアルゴリズムが必要な場合は、価格を降順に試すことをお勧めします。これにより、最初に残りの金額をできるだけ使い切ってから、残りをどのように埋めることができるかを確認できます.

また、数学を使用して、毎回開始する各食品アイテムの最大量を計算できるため、15.05 ドルの目標を超える組み合わせを試さないようにすることもできます。

このアルゴリズムは、完全な答えを得るために 88 通りの組み合わせを試すだけで済みます。

public class NPComplete {
    private static final int[] FOOD = { 580, 420, 355, 335, 275, 215 };
    private static int tries;

    public static void main(String[] ignore) {
        tries = 0;
        addFood(1505, "", 0);
        System.out.println("Combinations tried: " + tries);
    }

    private static void addFood(int goal, String result, int index) {
        // If no more food to add, see if this is a solution
        if (index >= FOOD.length) {
            tries++;
            if (goal == 0)
                System.out.println(tries + " tries: " + result.substring(3));
            return;
        }

        // Try all possible quantities of this food
        // If this is the last food item, only try the max quantity
        int qty = goal / FOOD[index];
        do {
            addFood(goal - qty * FOOD[index],
                    result + " + " + qty + " * " + FOOD[index], index + 1);
        } while (index < FOOD.length - 1 && --qty >= 0);
    }
}

2 つのソリューションを示す出力を次に示します。

9 回の試行: 1 * 580 + 0 * 420 + 2 * 355 + 0 * 335 + 0 * 275 + 1 * 215
88 回の試行: 0 * 580 + 0 * 420 + 0 * 355 + 0 * 335 + 0 * 275 + 7 * 215
試した組み合わせ: 88

Answer 13

@rcar's answerから学び、後で別のリファクタリングを行ったところ、次のようになりました。

私がコーディングする多くのものと同様に、CFML から CFScript にリファクタリングしましたが、コードは基本的に同じです。

私は彼の提案に、配列に動的な開始点を追加しました (値で配列を渡し、将来の再帰のためにその値を変更する代わりに)。 ))、そして、配列がコストでソートされると仮定することで、それを改善しました。中断により、209 回の再帰と 376 回のループ反復にまで減少しました。

アルゴリズムに他にどのような改善を加えることができますか?

function testCombo(minIndex, currentCombo, currentTotal){
    var a = 0;
    var CC = "";
    var CT = 0;
    var found = false;

    tries += 1;
    for (a=arguments.minIndex; a <= arrayLen(apps); a++){
        combos += 1;
        CC = listAppend(arguments.currentCombo, apps[a].name);
        CT = arguments.currentTotal + apps[a].cost;
        if (CT eq 15.05){
            //print current combo
            WriteOutput("<strong>#CC# = 15.05</strong><br />");
            return(true);
        }else if (CT gt 15.05){
            //since we know the array is sorted by cost (asc),
            //and we've already gone over the price limit,
            //we can ignore anything else in the array
            break; 
        }else{
            //less than 15.50, try adding something else
            found = testCombo(a, CC, CT);
        }
    }
    return(found);
}

mf = {name="mixed fruit", cost=2.15};
ff = {name="french fries", cost=2.75};
ss = {name="side salad", cost=3.35};
hw = {name="hot wings", cost=3.55};
ms = {name="mozarella sticks", cost=4.20};
sp = {name="sampler plate", cost=5.80};
apps = [ mf, ff, ss, hw, ms, sp ];

tries = 0;
combos = 0;

testCombo(1, "", 0);

WriteOutput("<br />tries: #tries#<br />combos: #combos#");

Answer 14

実際、アルゴリズムをもう少しリファクタリングしました。見逃していた正しい組み合わせがいくつかありましたが、それは、コストが 15.05 を超えるとすぐに戻ってきたという事実によるものでした。これが私の新しいアルゴリズムです：

<cffunction name="testCombo" returntype="numeric">
    <cfargument name="currentCombo" type="string" required="true" />
    <cfargument name="currentTotal" type="numeric" required="true" />
    <cfargument name="apps" type="array" required="true" />

    <cfset var a = 0 />
    <cfset var found = false /> 
    <cfset var CC = "" />
    <cfset var CT = 0 />

    <cfset tries = tries + 1 />

    <cfloop from="1" to="#arrayLen(arguments.apps)#" index="a">
        <cfset combos = combos + 1 />
        <cfset CC = listAppend(arguments.currentCombo, arguments.apps[a].name) />
        <cfset CT = arguments.currentTotal + arguments.apps[a].cost />
        <cfif CT eq 15.05>
            <!--- print current combo --->
            <cfoutput><strong>#CC# = 15.05</strong></cfoutput><br />
            <cfreturn true />
        <cfelseif CT gt 15.05>
            <!--<cfoutput>#arguments.currentCombo# > 15.05 (aborting)</cfoutput><br />-->
        <cfelse>
            <!--- less than 15.50 --->
            <!--<cfoutput>#arguments.currentCombo# < 15.05 (traversing)</cfoutput><br />-->
            <cfset found = testCombo(CC, CT, arguments.apps) />
        </cfif>
    </cfloop>
    <cfreturn found />
</cffunction>

<cfset mf = {name="Mixed Fruit", cost=2.15} />
<cfset ff = {name="French Fries", cost=2.75} />
<cfset ss = {name="side salad", cost=3.35} />
<cfset hw = {name="hot wings", cost=3.55} />
<cfset ms = {name="moz sticks", cost=4.20} />
<cfset sp = {name="sampler plate", cost=5.80} />
<cfset apps = [ mf, ff, ss, hw, ms, sp ] />

<cfset tries = 0 />
<cfset combos = 0 />

<cfoutput>
    <cfloop from="1" to="6" index="b">
        #testCombo(apps[b].name, apps[b].cost, apps)#
    </cfloop>
    <br />
    tries: #tries#<br />
    combos: #combos#
</cfoutput>

出力：

Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit = 15.05
Mixed Fruit,hot wings,hot wings,sampler plate = 15.05
Mixed Fruit,hot wings,sampler plate,hot wings = 15.05
Mixed Fruit,sampler plate,hot wings,hot wings = 15.05
false false false hot wings,Mixed Fruit,hot wings,sampler plate = 15.05
hot wings,Mixed Fruit,sampler plate,hot wings = 15.05
hot wings,hot wings,Mixed Fruit,sampler plate = 15.05
hot wings,sampler plate,Mixed Fruit,hot wings = 15.05
false false sampler plate,Mixed Fruit,hot wings,hot wings = 15.05
sampler plate,hot wings,Mixed Fruit,hot wings = 15.05
false
tries: 2014
combos: 12067

これにはすべての正しい組み合わせがあると思いますが、私の質問はまだ残っています: より良いアルゴリズムはありますか?

Answer 15

Here's concurrent implementation in Clojure. To calculate (items-with-price 15.05) takes about 14 combination-generation recursions, and about 10 possibility-checks. Took me about 6 minutes to calculate (items-with-price 100) on my Intel Q9300.

This only gives the first found answer, or nil if there is none, as that's all the problem calls for. Why do more work that you've been told to do ;) ?

;; np-complete.clj
;; A Clojure solution to XKCD #287 "NP-Complete"
;; By Sam Fredrickson
;;
;; The function "items-with-price" returns a sequence of items whose sum price
;; is equal to the given price, or nil.

(defstruct item :name :price)

(def *items* #{(struct item "Mixed Fruit" 2.15)
               (struct item "French Fries" 2.75)
               (struct item "Side Salad" 3.35)
               (struct item "Hot Wings" 3.55)
               (struct item "Mozzarella Sticks" 4.20)
               (struct item "Sampler Plate" 5.80)})

(defn items-with-price [price]
  (let [check-count (atom 0)
        recur-count (atom 0)
        result  (atom nil)
        checker (agent nil)
        ; gets the total price of a seq of items.
        items-price (fn [items] (apply + (map #(:price %) items)))
        ; checks if the price of the seq of items matches the sought price.
        ; if so, it changes the result atom. if the result atom is already
        ; non-nil, nothing is done.
        check-items (fn [unused items]
                      (swap! check-count inc)
                      (if (and (nil? @result)
                               (= (items-price items) price))
                        (reset! result items)))
        ; lazily generates a list of combinations of the given seq s.
        ; haven't tested well...
        combinations (fn combinations [cur s]
                       (swap! recur-count inc)
                       (if (or (empty? s)
                               (> (items-price cur) price))
                         '()
                         (cons cur
                          (lazy-cat (combinations (cons (first s) cur) s)
                                    (combinations (cons (first s) cur) (rest s))
                                    (combinations cur (rest s))))))]
    ; loops through the combinations of items, checking each one in a thread
    ; pool until there are no more combinations or the result atom is non-nil.
    (loop [items-comb (combinations '() (seq *items*))]
      (if (and (nil? @result)
               (not-empty items-comb))
        (do (send checker check-items (first items-comb))
            (recur (rest items-comb)))))
    (await checker)
    (println "No. of recursions:" @recur-count)
    (println "No. of checks:" @check-count)
    @result))