疑問

 投稿者：眞里  投稿日：2010年 8月21日(土)10時44分45秒
  異なる５つの数字を並べると必ず左から右、もしくは右から左へ向かって昇順をなす３つの数が存在する。
＜例＞
２，４，１，５，３→２，４，５

そこで、異なる何個の数字をならべると、必ず４個の昇順の数が存在するのか？
と考えた。
＜例＞
５，７，８，３，１，４，２，６
と８個の数字を並べてもだめである。

そこで
５，８，３，１，７，２，９，６，４
９個の数字を並べたら、８，７，６，４でok！


これは９個全ての順列で可能と言って構わないんでしょうか？
いろいろやってみて例外が作れなかったので判定お願いします。

これは一般化され
異なるｎ個の数字を並べるとき、必ずｒ個の昇順する数を含む
と断定できるためのｎとｒの関係はとれますか？ 		 

Re: 疑問

 投稿者：SECOND  投稿日：2010年 8月26日(木)15時24分27秒
  > No.1363[元記事へ]

眞里さんへのお返事です。

!全スキャンするだけの、ツールです。

!９個 でも 最長部分列の長さが、４に満たないものが、1764 個あります。
!１０個 で、全て４以上になります。3,682,800 通りですが、大して時間は
!かかりません。(Pen.3-500M でも10 分程)

! ～85696:   3  2  1  7  6  9  8  4  5 |増=(3)  3  7  9 |減=(3)  3  2  1
!～281644:   7  8  9  2  1  5  6  3  4 |増=(3)  7  8  9 |減=(3)  7  2  1
!～281996:   7  8  9  4  5  6  1  2  3 |増=(3)  7  8  9 |減=(3)  7  4  1

!最長増加部分列 Longest Increasing Subsequence の求め方については、

!----------------------------------------------
!<< 実験 >>
OPTION ARITHMETIC NATIVE

LET ss=1 !配列内、数列データーの始め( ss は、2 以上、0 以下でもよい)
LET mm=9 !配列内、数列データーの終り
LET rr=4 !　　　　最長部分列の、長さの下限
!
DIM n0(ss-1 TO mm),nn(ss-1 TO mm),  L(ss-1 TO mm),P1(ss-1 TO mm),P2(ss-1 TO mm)
!
FOR i=ss TO mm
   LET n0(i)=i
NEXT i
LET t00=TIME
CALL perm(n0,ss)
PRINT "perm.number=";num
PRINT "検査された数列の数=";num
PRINT "表示された数列の数=";num2
LET i=TIME-t00
IF i< 0 THEN LET i=i+86400
PRINT TRUNCATE(i,2);"秒　終了 ";

SUB perm(n0(),j)    !n0( ss)~n0( mm) の順列組合せを、nn( ss)~nn( mm) に作る。
   local i
   IF j<=mm THEN
      FOR i=ss TO ss+mm-j
         LET nn(j)=n0(i)
         swap n0(i),n0(ss+mm-j)
         CALL perm(n0,j+1)
         swap n0(i),n0(ss+mm-j)
      NEXT i
   ELSE
   !-----                                   !nn()= 全ての順列を、連射する。
      LET num=num+1
      IF MOD(num,10000)=0 THEN PRINT "perm.number=";num
      CALL check
      !! CALL check_all  !テスト用、全ての表示。
   END IF
END SUB

SUB check
   CALL LIS                                 !最長増加部分列の長さ inc を 求める。
   IF inc< rr THEN CALL LDS   !rr 未満ならば 最長減少部分列の長さ dec も 求める。
   IF inc< rr AND dec< rr THEN CALL print1  !昇・降とも 下限(rr)未満のみを、表示。
END SUB

SUB check_all
   CALL LIS                                 !最長増加部分列の長さ inc を 求める。
   CALL LDS                                 !最長減少部分列の長さ dec を 求める。
   CALL print1                              !全て表示。
END SUB

!----------------
SUB LIS                                     !Longest Increasing Subsequence
   LET inc=0
   LET L(ss-1)=0
   FOR i=ss TO mm
      LET k=ss-1
      FOR j=ss TO i-1
         IF nn(j)< nn(i) AND  L(k)< L(j) THEN LET k=j
      NEXT j
      LET L(i)=L(k)+1
      LET P1(i)=k
      !---
      IF inc< L(i) THEN
         LET inc=L(i)
         LET ini=i
      END IF
   NEXT i
END SUB

!----------------
SUB LDS                                     !Longest Decreasing Subsequence
   LET dec=0
   LET L(ss-1)=0
   FOR i=ss TO mm
      LET k=ss-1
      FOR j=ss TO i-1
         IF nn(j)> nn(i) AND  L(k)< L(j) THEN LET k=j
      NEXT j
      LET L(i)=L(k)+1
      LET P2(i)=k
      !---
      IF dec< L(i) THEN
         LET dec=L(i)
         LET dei=i
      END IF
   NEXT i
END SUB

!----------------
SUB strLIS(i)
   IF i< ss THEN EXIT SUB
   CALL strLIS(P1(i))
   LET w$=w$& USING$("###",nn(i))
END SUB

SUB strLDS(i)
   IF i< ss THEN EXIT SUB
   CALL strLDS(P2(i))
   LET w$=w$& USING$("###",nn(i))
END SUB

!----------------
SUB print1
   LET num2=num2+1
   LET w$=STR$(num)& ": "
   FOR i=ss TO mm
      LET w$=w$& USING$("###",nn(i))
   NEXT i
   LET w$=w$& " |増=("& STR$(inc)& ")"
   CALL strLIS(ini)
   LET w$=w$& " |減=("& STR$(dec)& ")"
   CALL strLDS(dei)
   PRINT w$
END SUB

END
 		 

戻る