順列・組み合わせ


ある問題解決のため、順列・組み合わせをasで組んでみました。
 
 
 
 
 

順列(nPr)
http://ja.wikipedia.org/wiki/%E9%A0%86%E5%88%97

組み合わせ(nCr)
http://ja.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E3%81%9B%E6%95%B0%E5%AD%A6
考え方は、はじめは「順列」から作りました。
「順列」の場合、rより小さい数がn個はいる配列をすべて作ります。
その中から、一つずつ重複のない配列だけを抽出する方法です。
「組み合わせ」は「順列」を引き出して、ソートして重複がない配列だけ抽出しました。

結果として、ちょっと重いです。
私のPCでは11P5ぐらいが限界でした。
取り急ぎの実用には問題ありませんでしたが、処理の分散などでブラッシュアップできそうです。

順列・組み合わせ – wonderfl build flash online

[sourcecode language=”as3″]
ackage {
import com.bit101.components.*;
import flash.display.MovieClip;
import flash.text.TextField;
import flash.text.TextFieldAutoSize;
import flash.text.TextFormat;
import flash.events.MouseEvent;
public class FlashTest extends MovieClip {
private var pn:InputText;
private var cn:InputText;
private var cr:InputText;
private var pr:InputText;
private var ta:TextArea;
private var pbtn:PushButton;
private var cbtn:PushButton;
private var p:Permutation;
private var c:Combination
private var ar:Array;
private var str:String;
private var func_cnt:uint;
private var l:uint;
private var n:uint;
private var r:uint;
private var N:String
private var nXr:String
public function FlashTest():void {
var tf:TextFormat=new TextFormat();
tf.size=24;

pn=new InputText();
pn.width=15;
pn.x=10;
pn.y=10;
pn.text="3"
addChild(pn);
//
var pt:TextField=new TextField();
pt.defaultTextFormat=tf;
pt.text="P";
pt.x=25;
pt.y=3;
pt.autoSize=TextFieldAutoSize.LEFT;
addChild(pt);
//
pr=new InputText();
pr.width=15;
pr.x=42;
pr.y=10;
pr.text="3"
addChild(pr);
//
pbtn=new PushButton();
pbtn.x=60;
pbtn.y=8;
pbtn.label="P submit"
addChild(pbtn);
pbtn.addEventListener(MouseEvent.CLICK,pclk);
//
//
cn=new InputText();
cn.width=15;
cn.x=210;
cn.y=10;
cn.text="3"
addChild(cn);
//
var ct:TextField=new TextField();
ct.defaultTextFormat=tf;
ct.text="C";
ct.x=225;
ct.y=3;
ct.autoSize=TextFieldAutoSize.LEFT;
addChild(ct);
//
cr=new InputText();
cr.width=15;
cr.x=244;
cr.y=10;
cr.text="2"
addChild(cr);
//
cbtn=new PushButton();
cbtn.x=265;
cbtn.y=8;
cbtn.label="C submit"
addChild(cbtn);

cbtn.addEventListener(MouseEvent.CLICK,cclk);

ta=new TextArea();
ta.x=5;
ta.y=30;
ta.width=400;
ta.height=300;
addChild(ta)

}

private function pclk(evt:MouseEvent):void{
var i:int;
p=new Permutation(uint(pn.text),uint(pr.text));
ar=p.getElements();
l=p.length;
nXr="nPr";
n=p.n;
r=p.r;
N="Permutation";
/**/
makeStr()
}
private function cclk(evt:MouseEvent):void{
var i:int;
c=new Combination(uint(cn.text),uint(cr.text));
ar=c.getElements();
l=c.length;
nXr="nCr";
n=c.n;
r=c.r;
N="Combination";
/**/
makeStr()
}
private function makeStr():void{
var i:int;
var _str:String=new String();
for(i=0;i<l;i++){
_str+=ar[i]+"\r";
}
str=_str + ta.text;
/**/
setStr();
}
private function setStr():void{
ta.text=str;
ta.text=nXr + " : "+ l + "\r"+ta.text;
ta.text="n: "+ n +" r:"+ r +"\r"+ta.text;
ta.text=N + "\r" + ta.text;
}
}
}

class Product {
private var elements:Array;
private var _n:uint;
private var _r:uint;
public function Product(n:uint,r:uint):void {
init(n,r);
}
public function get n():uint{
return _n;
}
public function get r():uint{
return _r;
}
public function get length():uint{
return elements.length;
}
public function getElements():Array{
return elements;
}
//
private function init(n:uint,r:uint):void{
var i:uint;
var ii:int;
_n = n;
_r = r;
elements=new Array();
//
for (i=0; i<Math.pow(_n,_r); i++) {
var parts:Array=new Array();
var cnt:uint=i;
for(ii=_r-1;ii>=0;ii–){
var ans:Number=Math.floor(cnt/Math.pow(_n,ii));
parts.push(ans)
cnt-=ans*Math.pow(_n,ii);
}
elements.push(parts);
}
}
}

class Permutation{
private var elements:Array;
private var _n:uint;
private var _r:uint;
//

public function Permutation (n:uint,r:uint):void {
_n = n;
_r = r;
init();
}
//
public function get n():uint{
return _n;
}
public function get r():uint{
return _r;
}
public function get length():uint{
return elements.length;
}
public function getElements():Array{
return elements;
}
//
private function init():void{
var i:uint;
var ii:int;
elements=new Array();
var product:Product=new Product(_n,_r);
var p_ar:Array=product.getElements();
for(i=0;i<product.length;i++){
var parts:Array=p_ar[i];
if (isNumbers(parts)) {
var ar:Array=new Array();
for(ii=0;ii<parts.length;ii++){
ar.push(parts[ii])
}
elements.push(ar);
}
}
elements.sort();
}

private function isNumbers (parts:Array):Boolean {
var i:uint;
var ii:uint;
for(i=0;i<_r;i++){
var n:uint=parts[i];
for(ii=i+1;ii<_r;ii++){
if(n==parts[ii]){
return false;
}
}
}
return true;
}
}

class Combination {
private var elements:Array;
private var _n:uint;
private var _r:uint;
private var p:Permutation;
private var p_ar:Array;
private var i:uint;
public function Combination(n:uint,r:uint):void {
_n=n;
_r=r;
init(n,r)
}
//
public function get n():uint{
return _n;
}
public function get r():uint{
return _r;
}
public function get length():uint{
return elements.length;
}
public function getElements():Array{
return elements;
}
//
private function init(n:uint,r:uint):void{
var i:uint;
var ii:uint;
var iii:uint;

p=new Permutation(_n,_r);
p_ar=p.getElements();
for(i=0;i<p_ar.length;i++){
p_ar[i].sort();
}
elements=new Array(p_ar[0])
for(i=1;i<p_ar.length;i++){
var cnt:uint=0;
var _ar:Array=p_ar[i];
for(ii=0;ii<elements.length;ii++){
if(String(_ar)!=String(elements[ii])){
cnt++;
if(cnt==elements.length){
elements.push(_ar);
break;
}
}
}
}
}
}
[/sourcecode]

では、実用例はどのようなものか。
複数の請求を出しているのに入金額の合計が請求額の合計以下だった場合、この組み合わせを使えばどの入金があったのか一発でわかるのではないのかなっと。
え?Flash製作ではなく、事務仕事に使うつもりです。