帶有依賴邊界的嵌套循環跳脫計數

只是出於好奇我試圖做到以下事情，結果對我來說並不那麼明顯; 假設我有與運行界限嵌套循環，例如：帶有依賴邊界的嵌套循環跳脫計數

t = 0 // trip count 
for l in 0:N 
    for k in 0:N 
    for j in max(l,k):N 
     for i in k:j+1 
      t += 1 

t is loop trip count

是有一般算法/方式（大於N^4明顯更好），以計算循環行程計數？

如果沒有，我會很好奇你會怎麼處理這個特定的循環。上面的迴路是對稱的（它是對稱的4級張量上的迴路），我也對檢測迴路對稱性的方法感興趣。

我工作的前提是迭代界限僅取決於常量或以前的循環變量。鏈接/期刊文章，如果你知道一個，會很棒。

來源

2010-05-14 Anycorn

這並不明顯，你想要實現 - 你可以從問題開始而不是解決方案？ – 2010-05-14 06:10:55

@Eli我提出了澄清 – Anycorn 2010-05-14 06:13:32

@aaa：那麼最後一個循環可以用't + = j + 1 - k'或類似的東西代替，但我仍然不知道你在做什麼 – 2010-05-14 06:22:17

如果你想知道有多少次內部循環：

for j in max(l,k):N

會被執行，只是計算：N - max(l, k)假設開放範圍，N + 1 - max(l, k)假設封閉的範圍內。

例如，如果：

l = 2 
k = 7 
N = 10

那麼它會在7，8，9，10（閉區間）運行，所以確實10 + 1 - 7 = 4倍。

來源

2010-05-14 06:30:06

我有興趣找出整個i，j，k，l被執行多少次，而不僅僅是一個循環 – Anycorn 2010-05-14 06:34:30

我想他想要一個沒有實際循環的't'的最終值的公式。 – IVlad 2010-05-14 07:27:26

相信內環將運行

t = 1/8 * (N^4 + 6 * N^3 + 7 * N^2 + 2 * N)

倍。

我沒有真正直接解決問題，我擬合了一個4階多項式表達式來準確計算t對於1到50之間的N，希望我能得到精確的擬合。

要計算我用

sum(sum(sum(sum(1,i,k,j+1),j,max(l,k),N),k,1,N),l,1,N)

這應該是實際運行的循環相當於確切噸。

data fit, log scale http://img714.imageshack.us/img714/2313/plot3.png

擬合對於N爲1至50的匹配準確，並計算它對於N = 100使用這兩種方法給出13258775。

編輯：這次演習採用開放源碼的代數系統maxima完成，這裏的實際源（輸出丟棄）：

nr(n):=sum(sum(sum(sum(1,i,k,j+1),j,max(l,k),n),k,1,n),l,1,n); 
M : genmatrix(lambda([i,j],if j=1 then i else nr(i)), 50, 2); 
coefs : lsquares_estimates(M, [x,y], y = A*x^4+B*x^3+C*x^2+D*x+E, [A,B,C,D,E]); 
sol(x):=ev(A*x^4+B*x^3+C*x^2+D*x+E, coefs); 
sol(N); 
S : genmatrix(lambda([i,j], if j=1 then i else sol(i)), 50, 2); 
M-S; 
plot2d([[discrete,makelist([M[N][1],M[N][2]],N,1,50)], sol(N)], [N, 1, 60], [style, points, lines], [color, red, blue], [legend, "simulation", sol(N)], [logy]); 
compare(nr(100),sol(100));

來源

2010-05-14 10:46:41 Unreason

答案是沒有，只要循環邊界可以依靠從外部變量以任意形式存在，因爲這將爲獲得積分級數的封閉形式提供一般手段。

看到這一點，考慮以下幾點：

for x in 0:N 
    for y in 0:f(x) 
    t += 1

的行程計數T（N）等於所述總和T（N）= F（0）+ F（1）+ F（2）+ F （3）+ ... + F（N-1）。因此，如果你可以得到t（N）的封閉形式公式，而不管f（）如何，你已經找到了一個生成封閉形式的非常一般的方法，我會說，因爲你在這裏對應的是一個積分和衆所周知，並非所有積分都允許封閉形式的配方。

來源

2010-05-15 19:40:04

帶有依賴邊界的嵌套循環跳脫計數

回答

相關問題