「3 Coins Shop」の商品価格

Question

###前提・実現したいこと
注）困っていることではありません。好奇心からの質問です。

下記のような課題があったとします。

1円、5円、10円、50円、100円、500円の各硬貨を3枚組み合わせて得られる金額をすべて列挙しなさい。
ただし、回答に使用できる組み合わせで5円、50円、500円の各硬貨は最大1枚までしか使用できません。

(JR新宿駅で「3CoinsShop」なる看板を見てふと思いついた問題です。)

期待される回答は下記のようになるはずですが。。。

金額 - 組合せ
  3円 -  1円×3枚
  7円 -  1円×2枚＋  5円×1枚
 12円 -  1円×2枚＋ 10円×1枚
 16円 -  1円×1枚＋  5円×1枚＋ 10円×1枚
 21円 -  1円×1枚＋ 10円×2枚
 25円 -  5円×1枚＋ 10円×2枚
 30円 - 10円×3枚
 52円 -  1円×2枚＋ 50円×1枚
 56円 -  1円×1枚＋  5円×1枚＋ 50円×1枚
 61円 -  1円×1枚＋ 10円×1枚＋ 50円×1枚
 65円 -  5円×1枚＋ 10円×1枚＋ 50円×1枚
 70円 - 10円×2枚＋ 50円×1枚
102円 -  1円×2枚＋100円×1枚
106円 -  1円×1枚＋  5円×1枚＋100円×1枚
111円 -  1円×1枚＋ 10円×1枚＋100円×1枚
115円 -  5円×1枚＋ 10円×1枚＋100円×1枚
120円 - 10円×2枚＋100円×1枚
151円 -  1円×1枚＋ 50円×1枚＋100円×1枚
155円 -  5円×1枚＋ 50円×1枚＋100円×1枚
160円 - 10円×1枚＋ 50円×1枚＋100円×1枚
201円 -  1円×1枚＋100円×2枚
205円 -  5円×1枚＋100円×2枚
210円 - 10円×1枚＋100円×2枚
250円 - 50円×1枚＋100円×2枚
300円 -100円×3枚
502円 -  1円×2枚＋500円×1枚
506円 -  1円×1枚＋  5円×1枚＋500円×1枚
511円 -  1円×1枚＋ 10円×1枚＋500円×1枚
515円 -  5円×1枚＋ 10円×1枚＋500円×1枚
520円 - 10円×2枚＋500円×1枚
551円 -  1円×1枚＋ 50円×1枚＋500円×1枚
555円 -  5円×1枚＋ 50円×1枚＋500円×1枚
560円 - 10円×1枚＋ 50円×1枚＋500円×1枚
601円 -  1円×1枚＋100円×1枚＋500円×1枚
605円 -  5円×1枚＋100円×1枚＋500円×1枚
610円 - 10円×1枚＋100円×1枚＋500円×1枚
650円 - 50円×1枚＋100円×1枚＋500円×1枚
700円 -100円×2枚＋500円×1枚

皆さんが得意としている言語で解くならどんなふうになりますか？

###回答例
javascriptで書いてみました。

{
  let arr=[1,1,1,5,10,10,10,50,100,100,100,500];
  let keys=[];
  for(let i = 0; i < arr.length; i++)
    for(let j = i+1; j < arr.length; j++)
      for(let k = j+1; k < arr.length; k++){
        let val = arr[i]+arr[j]+arr[k];
        keys[val]=val;
      };
  for(key in keys){ console.log(key); }
}

回答お待ちしていますm(_ _)m
16/05/06.11:05追記：できれば回答例の表記からは乖離したものがいただけると嬉しいです。

Answer 1

ruby で書いてみました。

require 'awesome_print'

ans = [1,1,1,5,10,10,10,50,100,100,100,500].combination(3).group_by {|coins| coins.inject(:+)}

ap ans.keys.sort
ans.sort.each { |k, v| p "#{k}: #{v}" }

実行結果

[
    [ 0] 3,
    [ 1] 7,
    [ 2] 12,
    [ 3] 16,
    [ 4] 21,
    [ 5] 25,
    [ 6] 30,
    [ 7] 52,
    [ 8] 56,
    [ 9] 61,
    [10] 65,
    [11] 70,
    [12] 102,
    [13] 106,
    [14] 111,
    [15] 115,
    [16] 120,
    [17] 151,
    [18] 155,
    [19] 160,
    [20] 201,
    [21] 205,
    [22] 210,
    [23] 250,
    [24] 300,
    [25] 502,
    [26] 506,
    [27] 511,
    [28] 515,
    [29] 520,
    [30] 551,
    [31] 555,
    [32] 560,
    [33] 601,
    [34] 605,
    [35] 610,
    [36] 650,
    [37] 700
]
"3: [[1, 1, 1]]"
"7: [[1, 1, 5], [1, 1, 5], [1, 1, 5]]"
"12: [[1, 1, 10], [1, 1, 10], [1, 1, 10], [1, 1, 10], [1, 1, 10], [1, 1, 10], [1, 1, 10], [1, 1, 10], [1, 1, 10]]"
"16: [[1, 5, 10], [1, 5, 10], [1, 5, 10], [1, 5, 10], [1, 5, 10], [1, 5, 10], [1, 5, 10], [1, 5, 10], [1, 5, 10]]"
"21: [[1, 10, 10], [1, 10, 10], [1, 10, 10], [1, 10, 10], [1, 10, 10], [1, 10, 10], [1, 10, 10], [1, 10, 10], [1, 10, 10]]"
"25: [[5, 10, 10], [5, 10, 10], [5, 10, 10]]"
"30: [[10, 10, 10]]"
"52: [[1, 1, 50], [1, 1, 50], [1, 1, 50]]"
"56: [[1, 5, 50], [1, 5, 50], [1, 5, 50]]"
"61: [[1, 10, 50], [1, 10, 50], [1, 10, 50], [1, 10, 50], [1, 10, 50], [1, 10, 50], [1, 10, 50], [1, 10, 50], [1, 10, 50]]"
"65: [[5, 10, 50], [5, 10, 50], [5, 10, 50]]"
"70: [[10, 10, 50], [10, 10, 50], [10, 10, 50]]"
"102: [[1, 1, 100], [1, 1, 100], [1, 1, 100], [1, 1, 100], [1, 1, 100], [1, 1, 100], [1, 1, 100], [1, 1, 100], [1, 1, 100]]"
"106: [[1, 5, 100], [1, 5, 100], [1, 5, 100], [1, 5, 100], [1, 5, 100], [1, 5, 100], [1, 5, 100], [1, 5, 100], [1, 5, 100]]"
"111: [[1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100]]"
"115: [[5, 10, 100], [5, 10, 100], [5, 10, 100], [5, 10, 100], [5, 10, 100], [5, 10, 100], [5, 10, 100], [5, 10, 100], [5, 10, 100]]"
"120: [[10, 10, 100], [10, 10, 100], [10, 10, 100], [10, 10, 100], [10, 10, 100], [10, 10, 100], [10, 10, 100], [10, 10, 100], [10, 10, 100]]"
"151: [[1, 50, 100], [1, 50, 100], [1, 50, 100], [1, 50, 100], [1, 50, 100], [1, 50, 100], [1, 50, 100], [1, 50, 100], [1, 50, 100]]"
"155: [[5, 50, 100], [5, 50, 100], [5, 50, 100]]"
"160: [[10, 50, 100], [10, 50, 100], [10, 50, 100], [10, 50, 100], [10, 50, 100], [10, 50, 100], [10, 50, 100], [10, 50, 100], [10, 50, 100]]"
"201: [[1, 100, 100], [1, 100, 100], [1, 100, 100], [1, 100, 100], [1, 100, 100], [1, 100, 100], [1, 100, 100], [1, 100, 100], [1, 100, 100]]"
"205: [[5, 100, 100], [5, 100, 100], [5, 100, 100]]"
"210: [[10, 100, 100], [10, 100, 100], [10, 100, 100], [10, 100, 100], [10, 100, 100], [10, 100, 100], [10, 100, 100], [10, 100, 100], [10, 100, 100]]"
"250: [[50, 100, 100], [50, 100, 100], [50, 100, 100]]"
"300: [[100, 100, 100]]"
"502: [[1, 1, 500], [1, 1, 500], [1, 1, 500]]"
"506: [[1, 5, 500], [1, 5, 500], [1, 5, 500]]"
"511: [[1, 10, 500], [1, 10, 500], [1, 10, 500], [1, 10, 500], [1, 10, 500], [1, 10, 500], [1, 10, 500], [1, 10, 500], [1, 10, 500]]"
"515: [[5, 10, 500], [5, 10, 500], [5, 10, 500]]"
"520: [[10, 10, 500], [10, 10, 500], [10, 10, 500]]"
"551: [[1, 50, 500], [1, 50, 500], [1, 50, 500]]"
"555: [[5, 50, 500]]"
"560: [[10, 50, 500], [10, 50, 500], [10, 50, 500]]"
"601: [[1, 100, 500], [1, 100, 500], [1, 100, 500], [1, 100, 500], [1, 100, 500], [1, 100, 500], [1, 100, 500], [1, 100, 500], [1, 100, 500]]"
"605: [[5, 100, 500], [5, 100, 500], [5, 100, 500]]"
"610: [[10, 100, 500], [10, 100, 500], [10, 100, 500], [10, 100, 500], [10, 100, 500], [10, 100, 500], [10, 100, 500], [10, 100, 500], [10, 100, 500]]"
"650: [[50, 100, 500], [50, 100, 500], [50, 100, 500]]"
"700: [[100, 100, 500], [100, 100, 500], [100, 100, 500]]"

Comments

[tkturbo]

回答ありがとうございます。
「配列」「combination」でググろうとすると「ruby 配列 combination」が検索候補に挙がってきますね。
ひょっとしてrubyで実装されたのが元祖なんでしょうか？

Answer 2

バッチファイルで作ってみました。

@echo off
setlocal ENABLEDELAYEDEXPANSION

set arr=1 1 1 5 10 10 10 50 100 100 100 500
call :prepare %arr%
for /L %%I in (1,1,%length%) do (
	set /A j = %%I + 1
	for /L %%J in (!j!,1,%length%) do (
		set /A k = %%J + 1
		for /L %%K in (!k!,1,%length%) do (
			set /A val = arr[%%I] + arr[%%J] + arr[%%K]
			set sval=00!val!
			set sval=!sval:~-3!
			set keys[!sval!]=!val!
		)
	)
)
for /F "tokens=2 delims==" %%A in ('set keys[') do echo %%A
goto :eof

:prepare
set /A length=0
:getlength_1
if "%1" == "" goto :eof
set /A length += 1
set arr[%length%]=%1
shift
goto :getlength_1

Comments

[tkturbo]

回答ありがとうございます。
MS-DOSで回答されるとは思ってませんでしたｗ

Answer 3

ちょっとした工夫を思いついてしまったので、そのコードを書いてしまいます(Java8)。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q34167_2 {
	public static void main(String[] args) {
		int[] coins = {1, 5, 10, 50, 100, 500};

		// 一枚しか使えない硬貨
		List<Integer> once = Arrays.asList(new Integer[]{5, 50, 500});
		List<Integer> total = new ArrayList<>();
		for (int i = 0; i < coins.length; i++) {

			// 一枚しか使えない硬貨を前のステップで使っていた場合には次の硬貨から、そうでなければ同じ硬貨から選択
			for(int j = once.contains(coins[i]) ? i + 1 : i; j < coins.length ; j++) {
				for (int k = once.contains(coins[j]) ? j + 1 : j; k < coins.length; k++){
					total.add(coins[i] + coins[j] + coins[k]);
				}
			}
		}
		total.stream().sorted().forEach(System.out::println);
	}

}

更にこれをなんとかStreamで書けないか試してみた…が、余り綺麗に書けなかったです。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Function;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Q34167_2 {
	public static void main(String[] args) {
		int[] coins = {1, 5, 10, 50, 100, 500};

		// 一枚しか使えない硬貨
		List<Integer> once = Arrays.asList(new Integer[]{5, 50, 500});
		
		// Stream内のListの最後の番号に応じ、次の番号を詰めたすべてのパターンのListのStreamを返す
		Function<List<Integer>, Stream<List<Integer>>> f = 
				e -> {
					int last = e.get(e.size() - 1);
					if (once.contains(coins[last])){
						last++;
					}
					return IntStream.range(last, coins.length).mapToObj(i -> {
						List<Integer> l = new ArrayList<>(e);
						l.add(i);
						return l;
					});
				};
		
		IntStream.range(0, coins.length).mapToObj(i -> {
			List<Integer> list = new ArrayList<>();
			list.add(i);
			return list;
		}).flatMap(f).flatMap(f)
		.mapToInt(e -> e.stream().mapToInt(i -> coins[i]).sum())
		.sorted().forEach(System.out::println);
	}

}

旧回答

この手の問題では、制約の厳しいものから考えることが鉄則です。今回の場合、「5円、50円、500円は最大1枚しか使えない」という制約があるので、これから考えます。

ある硬貨の組み合わせで、5円、50円、500円はそれぞれ「使う」か「使わない」かの2つの選択肢があります。全部使っても3枚に収まるので、各硬貨の選択は他の硬貨を使うか使わないかに影響を受けません。そうすると、2^3=8通りの組み合わせが出てきます。その「枚数」と「金額」をセットにしておきます。

残りの1円、10円、100円については3枚まで使えるわけですが、こう考えます。

1. それぞれ「使う」か「使わない」かで2つずつ選択肢
2. 使う硬貨が0種なら0円。

1種類ならそれを1~3枚のうち何枚使うか。
2種類ならどっちを2枚使うか、あるいはどちらも1枚ずつか。
3種類なら1枚ずつで確定

そして、最初の5円、50円、500円硬貨の枚数-金額ペアと照らし合わせ、合計3枚になるように足し合わせればできます。

Comments

[tkturbo]

回答ありがとうございます。
考え方はなるほどその通りですが、コード化するとこんな感じですかね？

{
　let t=[], v=[];
　/* 3枚まで使える部分全組合せ生成 */
　[1,10,100].forEach((a,i,ar)=>{
　　t[a]=a;
　　ar.forEach((b,j,br)=>{
　　　t[a+b]=a+b;
　　　br.forEach((c)=>{t[a+b+c]=a+b+c;});
　　});
　});
　/* 1枚しか使えない部分と合成 */
　t.forEach((e)=>{
　　let mod = e%3;
　　if(mod==0){ v[e]=e; }
　　else {
　　　[5,50,500].forEach((a, i, s)=>{
　　　　if(mod==2){v[e+a]=e+a;}
　　　　else{s.slice(i+1).forEach((b)=>{v[e+a+b]=e+a+b});}
　　　});
　　}
　});
　/* 1枚しか使えない硬貨のみで価格生成 */
　v[555]=555;
　v.forEach((e)=>console.log(e));
}

。。。かえって難しくなってしまった感が。。。orz
#コード整形のためインデントを全角スペースにしています。
#試すときは全角スペース→半角スペースなりタブなりに要変換

[tkturbo]

ちなみに、先に「1円、10円、100円」の組合せを生成しているのは、こちらの方が使用枚数判定が楽だったからです。

[swordone]

ええ、私もこの回答文を書いてる時にほかの人の簡素な回答が出てくるのを見て、「自分が逆にめんどくさいこと考えてるなぁ」と思って投稿を躊躇しておりました。

[tkturbo]

追加コードありがとうございます。
便利なライブラリや配列メソッドが列挙される中、ロジックで工夫できないかいろいろと考えていただいたのでこちらをベストアンサーとさせていただきたいと思います。

Answer 4

Scalaなら 1行で 書けます。

object Main extends App {
  List(1,1,1,5,10,10,10,50,100,100,100,500).combinations(3).foreach(println)
}

実行結果はこちら： http://scastie.org/16988

これはScalaが 順列、組み合わせ、冪集合 を生成する関数を標準で持っているからですね。
Scala Codebook 順列、組み合わせ、冪集合を生成する

Comments

[tkturbo]

回答ありがとうございます。
1Linerはすごいなぁ！
そしてScalaのcombinationsメソッド、便利だなぁ！

Answer 5

ライブラリありそうだなーと探してみました。

from itertools import permutations

arr = [1,1,1,5,10,10,10,50,100,100,100,500]
keys = set()
for x in permutations(arr, 3):
    keys.add(sum(x))
for x in sorted(keys):
    print x

from itertools import permutations
print sorted(set([sum(x) for x in permutations([1,1,1 ,5,10,10,10,50,100,100,100,500], 3)]))

実行結果はこちら:　http://ideone.com/Vy52JY

検索中に、こんな記事を見つけました。わけがわからない。
全ての組み合わせを作る

Comments

[tkturbo]

回答ありがとうございます。
おお、permutations便利だなぁ！
そしてリンク先はやっぱり難解だった件orz

[matobaa]

まちがえた……。 permutations ではなくて combinations のほうが速いですね。1320個 vs. 220個。

[tkturbo]

なるほど、permutationsだと順列([a,b]と[b,a]は別の組合せ)、combinationsだと順序無視の組合せ([a,b]と[b,a]は同じ組合せ)だから、計算量が違うのですね。
#しかし私の回答例でも無駄な計算をやっているのでそこは改善したいポイント。

Answer 6

こんにちは。

ちょっと頭休めにトライしてみました。
短いコードと言う意味では既に最適化できている印象ですし、アルゴリズムの解き方と言うよりは言語によってどのように書けるのかに興味をお持ちのように見えました。
C++は、そこそこ元ソースに忠実に書けます。C++11を使ってできるだけ元ソースに近づけてみました。

#include <type_traits>
#include <set>
#include <iostream>
using namespace std;

int main()
{
    unsigned arr[]={1,1,1,5,10,10,10,50,100,100,100,500};
    set<unsigned> keys;
    for (size_t i = 0; i < extent<decltype(arr)>::value; i++)
        for (size_t j = i+1; j < extent<decltype(arr)>::value; j++)
            for (size_t k = j+1; k < extent<decltype(arr)>::value; k++) {
                unsigned val = arr[i]+arr[j]+arr[k];
                keys.emplace(val);
            }
    for (auto key : keys) cout << key << "\n";

	return 0;
}

Comments

[tkturbo]

回答ありがとうございます。
やはりCをベースにした言語だと表現が似てしまいますねぇ。