組み合わせ問題をJavaで(重複組合せ)

Java
問題
赤、緑、青のボールがたくさんある。5個選ぶ場合の組み合わせを列挙せよ。

全部赤で5個でもいいし、赤2,緑2,青1でもいい。こういった同じ要素を繰り返し使える組み合わせを重複組合せと呼ぶ。
これも色々やり方がありそうだが非効率になってしまいそうだ。先人の知恵をありがたく拝借しよう。

//何かしら五個選ぶ...どうしよう
○○○○○

//2つ線を引いて3つの部屋に分けるという「神」発想
○|○○|○○ ->この場合赤が1,緑が2,青が2と考える

||○○○○○ ->これは赤0,緑0,青5

|○○○|○○ ->これは赤0,緑3,青2

○○○○○|| ->これは赤5,緑0,青0

縦棒を引いて3つの部屋に分けるという発想が素晴らしい。これでこの問題は7個ある場所から2つの縦棒の位置を決めるという。単なる組み合わせ問題になってしまった。(7C2)
単なる組み合わせ問題の解き方がわからない人はまずはこちらから学習してもらいたい。

7つの場所を0~6で表してその中のどこの部分が縦棒なのかを考えていく。

0 1 2 3 4 5 6 
  |         |

Javaで求めてみよう。

public class Main {

	public static void main(String[] args) {
		int n=5;//個数
		for(int i=0;i<n+1;i++){
			for(int j=i+1;j<n+2;j++){
				System.out.printf("%d,%d%n",i,j);
			}
		}
	}
}

[結果]

0,1
0,2
0,3
0,4
0,5
0,6
1,2
1,3
1,4
1,5
1,6
2,3
2,4
2,5
2,6
3,4
3,5
3,6
4,5
4,6
5,6

縦棒の組み合わせは上記の21個あることがわかった。
実際にプログラムで縦棒を入れながら赤(R)緑(G)青(B)で表示してみよう。

public class Main {

	public static void main(String[] args) {
		
		int n=5;
		for(int i=0;i<n+1;i++){	
			for(int j=i+1;j<n+2;j++){	
				//System.out.printf("%d,%d%n",i,j);	
				
				//7回回す
				for(int k=0;k<n+2;k++){	
					if(k<i){
						//kの値がiより小さい場合はRを出力
						System.out.print("R");
					}else if(k==i || k== j){
						//kの値がiとjと等しい場合は縦を出力
						System.out.print("|");
					}else if(k>j){
						//kの値がjより大きい場合はBを出力
						System.out.print("B");	
					}else{
						//それ以外はG
						System.out.print("G");
					}
				}
				System.out.println();
			}
		}
	}
}

[結果]

||BBBBB
|G|BBBB
|GG|BBB
|GGG|BB
|GGGG|B
|GGGGG|
R||BBBB
R|G|BBB
R|GG|BB
R|GGG|B
R|GGGG|
RR||BBB
RR|G|BB
RR|GG|B
RR|GGG|
RRR||BB
RRR|G|B
RRR|GG|
RRRR||B
RRRR|G|
RRRRR||

縦棒の位置を決めることによってすべての組み合わせが求められたようだ。

以下のようなフォーマットでの出力を考えよう。

 R G B
[0,0,5]
[0,1,4]
[0,2,3]
[0,3,2]
[0,4,1]
[0,5,0]
[1,0,4]
[1,1,3]
[1,2,2]
[1,3,1]
[1,4,0]
[2,0,3]
[2,1,2]
[2,2,1]
[2,3,0]
[3,0,2]
[3,1,1]
[3,2,0]
[4,0,1]
[4,1,0]
[5,0,0]

個数をカウントしていこう。まずRの個数だが下の図を見てもわかるがこれはiの値だ

ソースコードに落とし込もう。

public class Main {

	public static void main(String[] args) {
		int n=5;
		System.out.println(" R G B ");//追記
		for(int i=0;i<n+1;i++){
			int rCount=i;//iの値は赤の数
			for(int j=i+1;j<n+2;j++){
				int gCount=j-rCount-1;//緑の数はj-赤-1
				int bCount=n-rCount-gCount;//青はn-赤-緑
				System.out.printf("[%d,%d,%d]",rCount,gCount,bCount);	
				System.out.println();
			}
		}
	}
}

最初の問題の答えを求めることができた。重複組合せ問題は今回のように補助の縦棒を加えて単なる組み合わせ問題にしてしまうのがコツだ。

確認問題

Q1

以下のお菓子の中から2つを選択する(重複可)。ただし、合計金額は200円以内でなければならない。
アメ:30円
チョコ:120円
ガム:100円
ポテチ:80円
ビスケット:90円
条件を満たす組み合わせをすべて列挙せよ。
出力フォーマットは以下のようにすること
[アメ(30),アメ(30)]
[アメ(30),チョコ(120)]
.
.
.

[ヒント]
6C4と6C2の計算結果は同じなので今回は縦棒の位置を決めるよりお菓子の位置を決めたほうがラク
○○|||| ->アメが2つ
||○|○| ->ガム1,ポテチ1

[解答例]

public class Main {
	public static void main(String[] args) {
		Snack[] snacks={
				new Snack("アメ",30),
				new Snack("チョコ",120),
				new Snack("ガム",100),
				new Snack("ポテチ",80),
				new Snack("ビスケット",90),
		};
		
		for(int i=0;i<snacks.length;i++){
			for(int j=i+1;j<snacks.length+1;j++){
				if(snacks[i].price+snacks[j-1].price<=200){
					System.out.printf("[%s(%d),%s(%d)]%n",snacks[i].name,snacks[i].price,snacks[j-1].name,snacks[j-1].price);
				}
			}
		}	
	}	
}
class Snack{
	String name;
	int price;
	Snack(String name,int price){
		this.name=name;
		this.price=price;
	}
}

Q2

サイコロを3つ振って10になる組み合わせをすべて列挙せよ

[ヒント]
|○||○○|| ->2,4,4
○||||○|○ ->1,5,6
8C3の問題

[解答例]

public class Main {

	public static void main(String[] args) {
		for(int i=0;i<6;i++){
			int first=i+1;
			for(int j=i+1;j<7;j++){
				int second=j;
				for(int k=j+1;k<8;k++){
					int third=k-1;
					if(first+second+third==10){
						System.out.printf("[%d,%d,%d]%n", first,second,third);
					}
				}
			}
		}
	}
}

応用

先程のお菓子の問題は2つを選んだがこれを2つ以上ならOKという問題にしてみよう。

以下のお菓子の中から2つ以上を選択する(重複可)。ただし、合計金額は200円以内でなければならない。

アメ:30円
チョコ:120円
ガム:100円
ポテチ:80円
ビスケット:90円

条件を満たす組み合わせをすべて列挙せよ。
出力フォーマットは以下のようにすること(出力順は任意)

[ビスケット(90),ビスケット(90),]
[ポテチ(80),ビスケット(90),]
[ポテチ(80),ポテチ(80),]
[ガム(100),ビスケット(90),]
[ガム(100),ポテチ(80),]
[ガム(100),ガム(100),]
[チョコ(120),ポテチ(80),]
[アメ(30),ビスケット(90),]
[アメ(30),ポテチ(80),]
[アメ(30),ポテチ(80),ビスケット(90),]
.
.
.

解法1

この程度ならfor文ですべての組み合わせをとってもどうにかなる。

public class Main {
	public static void main(String[] args) {
		Snack[] snacks = { 
				new Snack("アメ", 30), 
				new Snack("チョコ", 120),
				new Snack("ガム", 100), 
				new Snack("ポテチ", 80),
				new Snack("ビスケット", 90), 
				};
		int maxMoney=200;//この金額を超えてはいけない
		int minNum=2;//2個以上
		//アメは0~6個の可能性
		for(int i=0;i<=maxMoney/snacks[0].price;i++){
			//チョコは0~1個の可能性
			for(int j=0;j<=maxMoney/snacks[1].price;j++){
				for(int k=0;k<=maxMoney/snacks[2].price;k++){
					for(int l=0;l<=maxMoney/snacks[3].price;l++){
						for(int m=0;m<=maxMoney/snacks[4].price;m++){
							boolean isCountOK=i+j+k+l+m >=minNum;
							boolean isPriceOK=i*snacks[0].price+j*snacks[1].price+k*snacks[2].price+l*snacks[3].price+m*snacks[4].price <=maxMoney;
							if(isCountOK && isPriceOK){
								System.out.printf("[%s%s%s%s%s]%n", 
										snacks[0].showInfoTimes(i),
										snacks[1].showInfoTimes(j),
										snacks[2].showInfoTimes(k),
										snacks[3].showInfoTimes(l),
										snacks[4].showInfoTimes(m));
							}
						}
					}
				}
			}
		}
	}
}
class Snack {
	String name;
	int price;

	Snack(String name, int price) {
		this.name = name;
		this.price = price;
	}
	String showInfo(){
		return String.format("%s(%d)", this.name,this.price);
	}
	String showInfoTimes(int times){
		String ret="";
		for(int i=0;i<times;i++){
			ret+=showInfo()+",";
		}
		return ret;
	}
}

実現はできたが力技感がすごい、しかもお菓子が増えたときの修正が面倒だ。
こういったときには再帰処理を検討してみるとよい。

解法2(再帰)

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

public class Main {

	public static void main(String[] args) {
		List<Snack> snacks=new ArrayList<>();
		snacks.add(new Snack("アメ", 30));
		snacks.add(new Snack("チョコ", 120));
		snacks.add(new Snack("ガム", 100));
		snacks.add(new Snack("ポテチ", 80));
		snacks.add(new Snack("ビスケット", 90));
		
		getSnack(200,snacks,0,"");
	}

	static void getSnack(int money, List<Snack> snacks, int count,String result) {
		//探索するお菓子がなくなったら終わり
		if(snacks.size()==0){
			//個数2個以上が今回の出力対象
			if(count>=2){
				System.out.println("["+result+"]");			
			}
		}else {
			//着目するお菓子(リストの先頭から取り出す(リストは短くなる))
			Snack snack = snacks.remove(0);	
			//アメだったら0~6個の可能性がある
			for (int i = 0; i <= money / snack.price; i++) {
				//アメの個数ごとに再帰処理(残金,一つ短くなったリスト,買った個数増やす,今買った要素を文字にして連結)
				getSnack(money - snack.price * i, new ArrayList<Snack>(snacks), count + i,result+snack.showInfoTimes(i));
			}
		}
	}
}

class Snack {
	String name;
	int price;

	Snack(String name, int price) {
		this.name = name;
		this.price = price;
	}
	String showInfo(){
		return String.format("%s(%d)", this.name,this.price);
	}
	String showInfoTimes(int times){
		String ret="";
		for(int i=0;i<times;i++){
			ret+=showInfo()+",";
		}
		return ret;
	}
}

再帰はロマンだ。ソースを見たときに処理が分かりづらいという弱点はあるが時として超絶なパワーを発揮する。プログラミング上級者を目指すならば必ずマスターしていかなければならない項目だ。

おまけ

1セント,10セント,25セントのコインを好きな枚数使う事ができる.
1234セントを支払う時最低何枚で払うことが出来るか?再帰を用いて求めよ。
import java.util. *;
public class Main {
	static int min=1000000; //答えとなる最小枚数(初期値として適当に大きな数字をいれておく)
	public static void main(String[] args){
		List<Integer> list=new ArrayList<>();	
		list.add(25);
		list.add(10);
		list.add(1);	
		change(1234,list,0,"");
		System.out.println("最小は"+min+"枚");	
	}
	static void change(int money,List<Integer> list,int num,String result){
		if(list.size()==0){
			if(money==0){
				if(num<min){
					min=num;
				}
				System.out.printf("%d枚%s%n", num,result);
			}				
		}else{
			int coin=list.remove(0);
			for(int i=0;i<=money/coin;i++){
				change(money-coin*i,new ArrayList<Integer>(list),num+i,result+coin+"("+i+")");
			}
		}
	}
}

コメント

タイトルとURLをコピーしました