整数の配列を考えると、このように数字の配列を考えるとおおよそ等しい距離

Question

を持つ配列のサイズを変更する：私はそれらの間にほぼ等しい距離を持つ配列にその配列のサイズを変更するために使用することができますどのようなアルゴリズム

[0, 99, 299, 498, 901] 

。または、別の方法では、概算最大公倍数で再サンプリングします。

[0, 99, 200, 299, 400, 498, 600, 700, 800, 901] 

エラーが2に設定されている元の値がいいだろう使用して、エラーバーは、溶液上方（設定できますので、最大公約数上記の例では約 100、従って結果は次のようになりあります）が、また、この結果に満足して次のようになります。

[0, 100, 200, 300, 400, 500, 600, 700, 800, 900]

アップデート2017年1月12日

var arr: [Int] = [0, 99, 299, 498, 901] 

var diffs = [Int]() 
var minGap: Int = 0 
for x in 0..<arr.count-1 { 
    let gap = arr[x+1] - arr[x] 
    diffs.append(gap) 
    if minGap == 0 || minGap > gap { 
     minGap = gap 
    } 
} 

var resamples = [Int]() 
for item in arr { 
    if let lastSample = resamples.last { 
     let n = Int((Float(item - lastSample)/Float(minGap)).rounded()) 
     let g = (item - lastSample)/n 
     var inserts = [Int]() 
     for x in 0..<n-1 { 
      let newSample = lastSample + ((x+1) * g) 
      inserts.append(newSample) 
     } 
     resamples.append(item) 
     resamples.append(contentsOf: inserts) 
    } else { 
     resamples.append(item) 
    } 
} 

Answer 1

次はJSの私の解決策です。私は最初に最小限のギャップを見つけて、元の値を変更することなく、それに応じて各アイテムとプロセスの間に収まるギャップの数を見つけようとします。

明らかに、このアルゴリズムを動作させるには、入力アレイを昇順でソートする必要があります。

var arr = [0, 99, 299, 498, 901], 
 
    gap = Math.min(...Array(arr.length-1).fill().map((_,i) => arr[i+1]-arr[i])), // Find the minimum gap 
 
    res = arr.reduce((p,c,i) => { var n = Math.round((c-p[p.length-1])/gap);  // Find howmany gaps are inbetween according to the minimum gap 
 
             g = Math.round((c-p[p.length-1])/n);  // Calculate the average gap top apply 
 
            return i ? p.concat(Array(Math.round(n-1)).fill().map((_,i) => p[p.length-1] + (i+1)*g),c) 
 
              : p.concat(c); 
 
           },[]); 
 
console.log(res);

は説明：

gap = Math.min(...Array(arr.length-1).fill().map((_,i) => arr[i+1]-arr[i])), 

まず、入力配列よりも1小さいサイズで新しい配列を設定します。 （Array(arr.length-1)）まず、定義されていない要素でそれを初期化し（.fill()）、次に.map()すべての要素をarr[i+1]-arr[i]で初期化します。今はギャップ配列があります。それを引数としてMath.min()の関数に展開します。それはMath.min(...Array(部分です。したがって、上記の場合、最小間隔は99となります。

res = arr.reduce((p,c,i) => { var n = Math.round((c-p[p.length-1])/gap); 
            g = Math.round((c-p[p.length-1])/n); 
           return i ? p.concat(Array(Math.round(n-1)).fill().map((_,i) => p[p.length-1] + (i+1)*g),c) 
             : p.concat(c); 
          },[]); 

.reduce()部分はややタフですが、それは簡単です。私たちの.reduce()オペレーションは、その引数（主にコールバック関数と呼ばれます）として関数をとり、配列アイテムのすべての反復でそれを実行します。このコールバック関数は、(p,c,i) => {... }で始まる部分です。これは矢印の機能です。基本的な機能と本質的に同じです。 x => xは、function(x) { return x;}またはx => {return x;}を意味します。我々のケースでは、（複数のステートメントのために）関数の本体を定義するために中かっこを使用しているので、return命令を使用する必要があります。

私たちの.reduce()は、空の配列である初期値を使用します。最後の部分は,[]);です。配列の項目ごとに呼び出されるコールバック関数は、3つの引数を渡します。(p,c,i)最初の空の配列はp（前の）引数に割り当てられ、現在の項目はc引数に割り当てられ、現在のインデックスはiに割り当てられます。コールごとの引数。

コールバックの本文では、2つの変数を定義しています。 nおよびg。

n = Math.round((c-p[p.length-1])/gap); 

p[p.length-1]p配列の最後の要素を返します。だから最初のターン。 i = 0の場合、p[0]はundefinedであり、Math.round((c-p[p.length-1])/gap);はNaN（数字ではありません）ですが、私たちは気にしません。

return i ? p.concat(Array(Math.round(n-1)).fill().map((_,i) => p[p.length-1] + (i+1)*g),c) 
     : p.concat(c); 

三項条件とは、

result = condition ? if true do this 
        : if false do this 

状態に応じて、いずれかの手順が実行され、結果が返されます。この場合、結果はpの値として返されます。私たちの場合はそう

i == 0（JSでfalse値）のみp.concat(c)を行い、新しいp値を返し、次の反復を続ける場合は、（新しいp、cとi値でコールバックを呼び出します。

iがfalseギャップに多くの中間要素を取る大きさの配列を作成する手段（0以外の値）を

p.concat(Array(Math.round(n-1)).fill().map((_,i) => p[p.length-1] + (i+1)*g),c) 

ように行う、のinitiない場合undefinedsで配列をalizeし、各要素をp[p.length-1] + (i+1)*gにマップし、この配列をp配列に連結し、最後にcを追加してp配列を返します。

p.concat(whatever...)命令は、pの要素と、引数として含まれる配列の「items」またはar引数を含む項目そのものからなる新しい配列を返します。というのは;

[1,2,3].concat([4,5,6],[7,8],9)だから、これはそれを説明する必要があります[1,2,3,4,5,6,7,8,9]

をもたらすであろう。

Answer 2

は基本的にあなたが等差数列に対して最小二乗回帰を使用したい：のReduの答えに基づいて、ここで彼のコードのスウィフトのバージョンがあります。

算術進行は、第1項、最終項、および共通の3項でパラメータ化できます。これらの3つの用語は、目的関数のパラメータを形成し、最小化しようとします。

各最適化ステップでは、試行算術進行のどの用語を元のセットに対して回帰する必要があるかを選択する必要があります。それはかなり難しいでしょうが、幸いにも両方のシリーズがソートされるので、これはO（N）トラバーサルになるはずです。

3つの用語の周りの制約は、印刷的に気に入っているセットになります。例えば、元系列が99,298,299であっても、100,200,300は99,198,297よりも好ましいでしょうか？

完全な答えが広すぎると感じるでしょう。おそらく少なくとも1週間の作業です。しかし、これが私がプロジェクトに着手する方法です。