5

n 個の値を持つ配列を作成する関数の下にあります (未回答の前の質問から)。配列の合計は $max に等しくなります。

function randomDistinctPartition($n, $max) {
  $partition= array();
  for ($i = 1; $i < $n; $i++) {
    $maxSingleNumber = $max - $n;
    $partition[] = $number = rand(1, $maxSingleNumber);
    $max -= $number;
  }
  $partition[] = $max;
  return $partition;
}

例: $n = 4 および $max = 30 に設定すると、次のようになります。

array(5, 7, 10, 8);

ただし、この関数は重複と 0 を考慮しません。私が望んでいて、達成しようとしているのは、事前定義された変数$maxに加算される一意の番号を持つ配列を生成することです。重複した数字と0 および/または負の整数はありません。

4

2 に答える 2

13

わかりました、この問題は実際には線形シーケンスを中心に展開しています。最小値が 1 の場合、次のシーケンスを検討してください。

f(n) = 1 + 2 + ... + n - 1 + n

このようなシーケンスの合計は次のようになります。

f(n) = n * (n + 1) / 2

例として、n = 4 の場合、合計は 10 です。つまり、4 つの異なる数値を選択している場合、ゼロもマイナスも含まない最小合計は 10 です。逆に、合計が 10 で、 4 つの数字の場合、(1,2,3,4) の組み合わせは 1 つだけです。

したがって、最初に、合計が少なくともこの下限と同じかどうかを確認する必要があります。それ以下の場合、組み合わせはありません。等しい場合、正確に 1 つの組み合わせがあります。高いと複雑になります。

ここで、制約が合計 12 で 4 つの数字があるとします。f(4) = 10 であることがわかりました。しかし、最初の (最小の) 数値が 2 の場合はどうなるでしょうか?

2 + 3 + 4 + 5 = 14

したがって、最初の数は 1 より大きくすることはできません。最初の数はわかっています。ここで、合計 11 (12 - 1) の 3 つの数字のシーケンスを生成します。

1 + 2 + 3 = 6
2 + 3 + 4 = 9
3 + 4 + 5 = 12

2 番目の数値は 1 ではないため、2 でなければなりません。3 で始まる 3 つの数の最小和は 12 であり、11 を追加する必要があるため、3 になることはできません。

ここで、足し合わせると 9 (12 - 1 - 2) になる 2 つの数が見つかり、3 が可能な最小値になります。

3 + 4 = 7
4 + 5 = 9

3 番目の数字は 3 または 4 です。3 番目の数字が見つかると、最後の数字が固定されます。可能な組み合わせは次の 2 つです。

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

これを一般的なアルゴリズムに変えることができます。次の再帰的な実装を検討してください。

$all = all_sequences(14, 4);
echo "\nAll sequences:\n\n";
foreach ($all as $arr) {
  echo implode(', ', $arr) . "\n";
}

function all_sequences($total, $num, $start = 1) {
  if ($num == 1) {
    return array($total);
  }
  $max = lowest_maximum($start, $num);
  $limit = (int)(($total - $max) / $num) + $start;
  $ret = array();
  if ($num == 2) {
    for ($i = $start; $i <= $limit; $i++) {
      $ret[] = array($i, $total - $i);
    }
  } else {
    for ($i = $start; $i <= $limit; $i++) {
      $sub = all_sequences($total - $i, $num - 1, $i + 1);
      foreach ($sub as $arr) {
        array_unshift($arr, $i);
        $ret[] = $arr;
      }
    }
  }
  return $ret;
}

function lowest_maximum($start, $num) {
  return sum_linear($num) + ($start - 1) * $num;
}

function sum_linear($num) {
  return ($num + 1) * $num / 2;
}

出力：

All sequences:

1, 2, 3, 8
1, 2, 4, 7
1, 2, 5, 6
1, 3, 4, 6
2, 3, 4, 5

これの 1 つの実装は、すべてのシーケンスを取得し、ランダムに 1 つを選択することです。これには、可能なすべての組み合わせを均等に重み付けするという利点があります。これは、あなたがしていることに有用または必要である場合とそうでない場合があります。

これは、合計が大きい場合や要素の数が多い場合には扱いにくくなります。その場合、上記のアルゴリズムを変更して、すべての値ではなく から$startまでの範囲のランダムな要素を返すことができ$limitます。

于 2010-05-08T15:22:53.030 に答える
2

私は「三角形の下の領域」の式を使用します...cletus（！？）のように私は本当に物事にもっと注意を払う必要があります...

とにかく、このソリューションは今ではかなりエレガントだと思います。すべての要素間に必要な最小間隔を均等に適用し、ギャップ（分布）を均等にスケーリングして元の合計を維持し、非再帰的に（並べ替えを除いて）ジョブを実行します。

長さnの乱数の配列a（）が与えられます

ソートインデックスs（）を生成します

ソートされた間隔a（s（0））-a（s（1））、a（s（1））-a（s（2））などで作業します

  1. 各間隔を必要な最小分離サイズ（たとえば1）だけ増やします（これは必然的に「ランダム性」を歪めます）

  2. 間隔を追加せずに系列の合計を元の状態に戻すために計算された係数で各間隔を減らします。

各シリーズに1を追加すると、シリーズの合計が1*len増加します。

各系列間隔に1を追加すると、合計が次のように増加します。len *（len + 1）/ 2 //（？パスカルの三角形）

ドラフトコード：

$series($length);        //the input sequence 
$seriesum=sum($series);  //its sum
$minsepa=1;              //minimum separation

$sorti=sort_index_of($series) //sorted index - php haz function?

$sepsum=$minsepa*($length*($length+1))/2; 
//sum of extra separation

$unsepfactor100=($seriesum*100)/($seriesum+sepsum); 
//scale factor for original separation to maintain size
//(*100~ for integer arithmetic)

$px=series($sorti(0)); //for loop needs the value of prev serie

for($x=1 ; $x < length; $x++)
{ $tx=$series($sorti($x));             //val of serie to
  $series($sorti($x))= ($minsepa*$x)   //adjust relative to prev
                     + $px 
                     + (($tx-$px)*$unsepfactor100)/100; 

  $px=$tx;                             //store for next iteration 
  }
  • すべての間隔は一定に短縮されます（非ランダムワーピングファクター）
  • 分離は1以外の値に設定できます
  • 実装は、丸め誤差に対応するために注意深く調整する必要があります（私は通常、テストと「キャリブレーション」
    を行います）。おそらく、すべてを最大15までスケールアップしてから、後で元に戻します。正しく行われれば、間隔は存続するはずです。

ソートインデックスが生成されたら、インデックスの順序をシャッフルして値を複製し、衝突した一連のシーケンスでの実行を回避します。（または、順序が重要でない場合は、最終出力をシャッフルします）

デュープのシャッフルインデックス：

for($x=1; $x<$len; $x++)                   
{ if ($series($srt($x))==$series($srt($x-1)))
  { if( random(0,1) ) 
    { $sw= $srt($x);
      $srt($x)= $srt($x-1);
      $srt($x-1)= $sw;
  } } }

ある種の最小限の妨害は、質問によって求められた最小の「ランダムな」量よりも多く移動するのではなく、必要な最小限の部分で複製を分割することによって「ランダムなシーケンス」に対して行うことができます。

ここでのコードは、重複しているかどうかに関係なく、すべての要素を最小の区切りで区切ります。コードを変更して、シリーズ（sorti（n0：n1..len））を調べ、各重複のsepsumを+ = minsep *（len-n）として計算することにより、重複のみを分離することができます。次に、調整ループは、調整を適用する前に、重複を再度テストする必要があります。

于 2010-05-09T18:45:14.347 に答える