数値の掛け算の組み合わせを知りたい

Question

以下のように配列で、数値が与えられます。
$prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];

この中から組み合わせで掛け算した結果を取得したいです。
また、何個の数値の掛け算の結果かも取得したいです。

結果イメージとして

[
15=>2, // 3*5
21=>2, // 3*7
・・・(略)・・・
105=>3, // 3*5*7
165=>3, // 3*5*11
・・・(略)・・・
1155=>4, // 3*5*7*11
・・・(略)・・・
]

(演算結果)=>(かけた数値の個数)
のような結果一覧を取得したいです

よろしくお願いします。

Answer 1

難しいことを考えずにサッと解くなら再帰すると簡単でしょうかね。

<?php
$prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];

$result = [];

function func(&$result, $list, $i = 0, $val = 1, $cnt = 0, $expr = "")
{
    if ($i < count($list)) {
        func($result, $list, $i+1, $val*$list[$i], $cnt+1, "$expr*{$list[$i]}");
        func($result, $list, $i+1, $val, $cnt, $expr);
    } else if ($val > 1) {
        $result[] = [$val, $cnt, trim($expr, '*')];
    }
}

func($result, $prime_list);
//print_r($result);

foreach ($result as list ($val, $cnt, $expr)) {
    echo "$expr = $val ... ($cnt)\n";
}

最後の引数 $expr は結果の確認のために設けているだけなので無くてもいいです。

Comments

[ngyuki]

項が一つしかないものを除外するのであれば

} else if ($val > 1) {

を

} else if ($cnt > 1) {

とかにしてください。

[退会済みユーザー]

私にとって、一番理解しやすかったものを選ばせていただきました。
再帰処理以外での方法も、後学のために試してみようかと思います。

多くの回答ありがとうございました。

Answer 2

実装方針だけを述べます。

1. 0 か 1 を 10 個並べた組み合わせを順番に得ることができる stream をつくる。
2. 得られた item (0,1 を要素とする 10 個の配列) に対して
   val = 1
   num = 0
   for i on [0..10]
   if item[i] != 0
   val *= prime_list[i]
   num ++
   として、掛け算の結果 (val)、掛け算につかった要素の個数 (num) を得ます。
3. 上で得た val, num を 結果として蓄積します。
   蓄積方法としては、 キーを val, 値を num にした hash を使う。

(素数の掛け算なので、val には重複がない。
もし、素数のリストでなければ、掛け算結果に重複があり得えます。
その場合は hash の val は 配列にする)

すでに別の回答にあるように
1 の部分は strem でなく、 for でループを組んで 0 か 1 を 10 個並べた組み合わせを
得ることも可能です。

上の方法では、同じ掛け算を何回も行うことになります。
掛け算の実施回数を減らことを考えるなら、
使う要素の数が１つ増えたときは 過去の掛け算の結果に 増えた要素を１回 掛け算するようにする
という工夫をすることも可能です。

Answer 3

2ビット数という事に注目すると 簡単に処理出来ると思います

2ビットというか各項を1ビットで表現する感じでしょうかね。

試しにやってみました。

<?php
$prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];
$result = [];
$max = 1 << count($prime_list);

for ($i=0; $i<$max; $i++) {
    $val = 1;
    $cnt = 0;
    $expr = "";
    for ($j=0,$k=$i; $k; $j++,$k=$k>>1) {
        if ($k & 1) {
            $val *= $prime_list[$j];
            $cnt++;
            $expr = "$expr*{$prime_list[$j]}";
        }
    }
    if ($cnt > 1) {
        $result[] = [$val, $cnt, trim($expr, '*')];
    }
}

foreach ($result as list ($val, $cnt, $expr)) {
    echo "$expr = $val ... ($cnt)\n";
}

---

あるいは無駄に配列関数を駆使してみたり

<?php
$prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];
$result = [];
$max = 1 << count($prime_list);

for ($i=0; $i<$max; $i++) {
    $arr = array_filter(array_map(
        function ($a, $b) { return $a * $b; },
        $prime_list,
        preg_split("//", strrev(sprintf("%b", $i)), -1, PREG_SPLIT_NO_EMPTY)
    ));
    if (count($arr) > 1) {
        $result[] = [array_product($arr), count($arr), implode("*", $arr)];
    }
}

foreach ($result as list ($val, $cnt, $expr)) {
    echo "$expr = $val ... ($cnt)\n";
}

Comments

[YukiMiyatake]

２進数と書いたつもりが　ミスってましたすみません

Answer 4

こんにちは。

問題の核になるのは

$prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31]; 

という配列を集合とみて、これの冪集合（power set）の要素をもれなく
生成するロジックをどう書くか？ということかと思いました。

なので、冪集合を作り出すロジックを調べるなどして、以下が出来ました。

<?php

# ---------------------------------------------
# 与えられた配列を集合とみなして、これの冪集合
# に相当する配列を作成して返す。
# ---------------------------------------------
function beki($list) {
  $result = []; 
  $n = count($list);
  
  for ( $i =0; $i < (1<<$n); ++ $i ) { 
    $a = []; 
    for ( $j = 0; $j < $n; ++ $j ) { 
      if ( ($i >> $j) & 1 ) { 
        $a[] = $list[$j];
      }   
    }   
    $result[] = $a; 
  }
  return $result;
}

# 与題の素数リスト
$prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];

# べき集合に相当するリストを作成する。
$power_list = beki($prime_list);

# 与題に沿った出力をするための配列作成
$results = array();

foreach ( $power_list as $list ) { 
  if ( count($list)==0 ) continue;

  $product = 1;
  foreach ( $list as $e ) 
    $product *= $e; 

  $results[$product] = count($list);
}

# 確認のための出力
foreach( $results as $product => $count ) { 
  echo "$product => $count\n"; 
}

これを実行すると、以下のような出力を得ました。

3 => 1

5 => 1
15 => 2
7 => 1
21 => 2
・・・
2865149859 => 8
4775249765 => 8
14325749295 => 9
6685349671 => 8
20056049013 => 9
33426748355 => 9
100280245065 => 10

そして電卓で、3×5×・・・×29×31　を計算したら確かに
100280245065
となって出力の最終行と合っていて、正直ほっとしている次第です。

面白い問題、ありがとうございました。

Answer 5

2 がリストに無いのが気になりますが・・

まず前提として、同じ素数は1回しか使われないですか？
例えば 3x3 はNG

私ならそうですね、この程度の数なら最初に 全パターンのリストを作ります
$prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];
各素数は １０個ですので
2の10乗の組み合わせです。

全ての組み合わせに関してループし、array_push(演算結果,個数)
をすれば良いでしょう

全ての組み合わせは色々とやり方はありますが
愚直に10重ループにしても出来ますし
2ビット数という事に注目すると 簡単に処理出来ると思います