みんなの「教えて(疑問・質問)」にみんなで「答える」Q&Aコミュニティ

こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

順列文字の生成処理

次のような左端の番号に対応した右側の文字列を作りたいのです。
これらの4個の文字列は、重複無しの順列になります。
下表では文字列が4個ですが、実際には7個程度まで生成したいのです。7個の場合は合計1*2*3*4*5*6*7=5040個になります。
言語はFORTRANですがCでも、あるいは手順説明でも良いです。文字列でなくともn桁数字あるいは配列でも良いです。c++のクラス処理も候補かも知れませんが、FORTRANで書くには荷が重いです。再帰処理は何とかなるかも知れませんが、できれば無しを希望します。
4個程度ならデータとして書けば済みますが、6,7個となるとそうは行きませんので、プログラムで生成したいのです。処理時間は問題になりません。
N個の処理を使ってn+1個の処理の形式で大分頭を悩ませましたが、ギブアップ気味です(まだ1日程度ですが)。虫の良いお願いですが奇特な諸兄のお知恵を拝借したく存じます。


1: 1234
2: 2134
3: 1324
4: 3124
5: 2314
6: 3214

7: 1243
8: 2143
9: 1423
10: 4123
11: 2413
12: 4213

13: 1342
.
.
18: 4312

19: 2341
.
.
24: 4321

投稿日時 - 2018-12-13 16:19:17

QNo.9567428

暇なときに回答ください

質問者が選んだベストアンサー

#4 & #5 & #9です。
逆の手続きも欲しがっているようなので,fortranで作ってみた。ついでに以前のコードも手直ししてある。しかし本質的には以前のコードと何も変わっていません。一応n=4のときに全ケースで,場合番号から組み合わせ文字列を作り,さらにその組み合わせ文字列から場合番号を再計算するようになっています。当然ですが,最初の場合番号と同じものが返されます。

program main
implicit none
integer::n,nt,nt1,np
integer,allocatable,dimension(:)::nn
integer,allocatable,dimension(:)::pp
n=4
allocate(nn(n-1))
allocate(pp(n))
np=factorial(n)

do nt=1,np
call n2f(nt,n,nn)
Call f2p(n,nn,pp)
call p2f(n,nn,pp)
nt1=f2n(n,nn)
print*,nt,":",pp,":",nt1
end do

contains

integer function factorial(n)
integer::n
integer::n1
factorial=1
n1=n
do
factorial=factorial*n1
n1=n1-1
if (n1==1) exit
end do
end function

subroutine p2f(n,nn,pp)
integer::n
integer,dimension(*)::nn,pp
integer::i,i2,c
do i=1,n-1
c=0
do i2=1,i
if(pp(i2)>pp(i+1))c=c+1
end do
nn(i)=c
end do
end subroutine

integer function f2n(n,nn)
integer::n
integer,dimension(*)::nn
integer::i,n1
n1=n
f2n=0
do i=1,n-1
f2n=(f2n*n1)+nn(n-i)
n1=n1-1
end do
f2n=f2n+1
end function

subroutine n2f(nt,n,nn)
integer::nt,n
integer,dimension(*)::nn
integer::i,nt1
nt1=nt-1
do i=1,n-1
nn(i)=mod(nt1,i+1)
nt1=int(nt1/(i+1))
end do
end subroutine

subroutine f2p(n,nn,pp)
integer::n
integer,dimension(*)::nn,pp
integer::i,j,j2,t
do i=1,n
pp(i)=i
end do
do i=n-1,1,-1
j=nn(i)
t=pp(i+1-j)
do j2=i+1-j,i
pp(j2)=pp(j2+1)
end do
pp(i+1)=t
end do
end subroutine
end program

投稿日時 - 2018-12-17 18:04:27

補足

実装する時間がとれましたので、現方法(no1さんの改善ベース)とこのno.11さんの新方法とを比較検証しました。
分析したい事象データ数は150万個ほどで、文字列の並び(次元)の数を5個と6個で実行しました。結果は同じでしたので正しく実装されています。
6個の場合の実行時間
現方法 8’51” 新方法 9’14” 
5個の場合(6個とは試す数が少ないですが、比較には問題ないです)
現方法 4’35” 新方法 3’43”
となって、次元数が6個と大きいと現方法が有利、5個と少ないと新方法有利です。
実装方法には大きな違いがあって、現方法ではパターン(並びの種類数、6個で720個)用のテーブルを大量に用意しなければなりませんが、新方法では不要な効果があります。これは実装上のかなりの制約になっています。
今後はケースによってつかいわけることになろうかと思っています。
順方向と逆方向まで完全なソースをご教示頂きありがとうございました。

投稿日時 - 2018-12-20 13:18:20

お礼

逆の手続きまでFORTRANでご教示頂き大変ありがとうございます。
効果を確認の上、結果をこの回答番号の補足コメントで後程報告させていただきます。
とりあえずお礼まで。

投稿日時 - 2018-12-17 18:47:42

ANo.11

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(11)

ANo.10

>追加
>ただ期待の文字列かは、
>0+1+2+3+4+5+6ではだめで、全ての文字列がそろっているかになるはずです

コードをよく見ていただきたいのですが...
篩を2段階にすることで高速化を目指しています。

つまり
>・7つの文字列の合計が0+1+2+3+4+5+6 か?
これを満足していなかったらFalse("NG")とすることで、
より早く判定ルーチンから抜け
満足していたら、続いて
>・0,1,2,3,4,5,6の文字列があるか?
をチェックしています。

投稿日時 - 2018-12-16 07:35:14

お礼

なるほど、そうでしたか。コード見てそれのようにわかりました。
このふるいの効果は、すべての文字がそろっているかの判定をスキップできることなのですね。
ただNo1さんの方法では7重ループの外側の方からふるいにかける工夫ができますので、そちらの方が期待文字列かどうかの判定回数は少なくなるように思います。
話題がそれますが、No8さんへのお礼に述べていますが、
組わ合わせ文字列から、場合番号への変換と、場合番号から組み合わせ文字列への変換の2種類のニーズがあって、最初の質問では後者のことについてでした。ご提案頂いた頂いた方法は、すべての組み合わせ文字列を順番に生成する方法に関することで、これを前者に適用するためには、指定の文字列を組み合わせ文字列テーブルから検索することになります(現実装)。
現実装では速度的、サイズ上で少々不満なので改善方法を模索しています。

投稿日時 - 2018-12-16 09:30:53

ANo.9

#4 & #5です。
fortranが好きそうなので,fortranで同じプログラムを書いてみた。
なお,#4でのEnd Subの直前のNextは単なる消し忘れです。

program main
implicit none
integer::k,n,np,nt,nt1
integer,allocatable,dimension(:)::nn
integer,allocatable,dimension(:)::pp
n=7
allocate(nn(n-1))
allocate(pp(n))
np=factorial(n)
do nt=0,np-1
nt1=np-1-nt
Call n2f(nt1,n,nn)
Call f2p(n,nn,pp)
print*,nt+1,": ",pp
end do
contains
integer function factorial(n)
integer::n
integer::n1
factorial=1
n1=n
do
factorial=factorial*n1
n1=n1-1
if (n1==1) exit
end do
end function
subroutine n2f(nt1,n,nn)
integer::nt1,n
integer,dimension(*)::nn
integer::i
do i=1,n-1
nn(i)=0
end do
k=1
Do
k=k+1
nn(n-k+1)=mod(nt1,k)
nt1=int(nt1/k)
if (nt1<=0) exit
end do
end subroutine
subroutine f2p(n,nn,pp)
integer::n
integer,dimension(*)::nn,pp
integer::i,j,j2,k2,t
do i=1,n
pp(n+1-i)=i
end do
k=n-1
k2=n-1
do i=1,k
j=nn(i)
t=pp(k2+1-j)
do j2=k2+1-j,k2
pp(j2)=pp(j2+1)
end do
pp(k2+1)=t
k2=k2-1
end do
end subroutine
end program

投稿日時 - 2018-12-15 18:01:37

補足

今コードをコピペしてGFORTRANで実行するとなんのエラーもなく5040個の組み合わせがPRINTされました。コードの完成度と移行性が素晴らしいです。普段使わない記述があるのに!!
動作を読んでみます。
(送れるチップの数が残りわずかになりました)

投稿日時 - 2018-12-15 21:57:36

お礼

FORTRANのコードで例示頂きありがとうございます。これならスムーズに確認することができそうです。

投稿日時 - 2018-12-15 22:26:08

ANo.8

N枚のカードを並べるときの 順列・組み合わせの数はN! (Nの階乗) ですが
その 1~N!の番号のうち 任意の番号を指定したら、
使わない値も埋めてあるテーブル(配列)を事前に作ることなく、
計算一発でその値を取り出せるような、便利な関数はないものか
ということですよね。
(重複ありだと簡単ですけど、重複なしの値だと直線的に並ばないので
 ループなしの計算で出すのは、難しそうな感じですね。
 N番目の素数を求めることがループなしの計算ではできなので、
 暗号が破り難いのと似てるような感じなのかも。)

用途次第だとは思いますが、
もし、番号を指定して同じ番号で同じ結果である必要がなく
N桁の重複なしのランダムな値を生成するだけでいいなら
・ランダム関数をマイクロ秒等を使って同じ初期値にならないようにしておく
・1~Nの値の入ったN個の配列からランダムに1つ選ぶ
・配列から上の数値を取り除いて、N-1個からランダムに1つ選ぶ
・上を1個になるまで繰り返す
とすれば、N回の計算で終わりますが、
用途として合わないのでしょうね。

投稿日時 - 2018-12-15 13:57:38

お礼

最初の質問はその通りです。
やはり直線的に並ばないので難しいわけですね。この直線的に並ばないという表現がなるほどです。
後段のご提案は合わないですね。

その後、no1さんの方法でテーブルをつくり、それを検索する方法(検索の必要性はまだ説明してないですが)で、目的の検証を進めましたが、やはりこの方法では時間がかかることがわかりました。桁数は7桁もいらず、5-6桁程度になっています。
最初の質問は、組み合わせ総数の中の番号から、対応する組み合わせを求めることでしたが、前段階として、組み合わせの一つが与えられて、それに対応する組み合わせ総数の内の一つの番号をつくることも必要で、時間メモリ制約は後者の方です。この方法についても未解決ですが、別途質問項目を挙げてみたいと思います。その際はよろしく。

投稿日時 - 2018-12-15 21:31:00

ANo.7

こんなアイデアはいかがでしょうか?

7桁を例に説明します。
7進数で 0000000 ~ 6666666 までの文字列を組立
総当たりで、期待の文字列かどうかをチェックし
期待の文字列だけを書き出します。

期待の文字列かどうかは
・7つの文字列の合計が0+1+2+3+4+5+6 か?
・0,1,2,3,4,5,6の文字列があるか?
でチェックします。

以下、VBAのサンプルです。

なお、
総当たりの範囲を
7進数で 0000000 ~ 6666666
ではなく、
7進数で 0123456 ~ 6543210
とすれば、若干性能を改善できるかもしれません。

Option Explicit

Sub Test2()
 Dim wkC As Long
 Dim MyCode As String
 Dim HitCount As Long
 HitCount = 0
 'For wkC = 0 To 7 ^ 7
 For wkC = 22875 To 800667
  MyCode = Get7Code(wkC)
  If MyCode <> "NG" Then
   HitCount = HitCount + 1
   ThisWorkbook.Sheets(1).Cells(HitCount, 1).Value = "'" & MyCode
  End If
 Next wkC
End Sub

Function Get7Code(Myi As Long) As String

 Dim wki(7) As Long
 Dim wkT As String
 Dim i As Long
 
 i = Myi
 
 wki(7) = i \ (7 ^ 6)
 i = i - wki(7) * (7 ^ 6)
 wki(6) = i \ (7 ^ 5)
 i = i - wki(6) * (7 ^ 5)
 wki(5) = i \ (7 ^ 4)
 i = i - wki(5) * (7 ^ 4)
 wki(4) = i \ (7 ^ 3)
 i = i - wki(4) * (7 ^ 3)
 wki(3) = i \ (7 ^ 2)
 i = i - wki(3) * (7 ^ 2)
 wki(2) = i \ (7 ^ 1)
 i = i - wki(2) * (7 ^ 1)
 wki(1) = i \ (7 ^ 0)

 Get7Code = "NG"

 If wki(7) + wki(6) + wki(5) + wki(4) + wki(3) + wki(2) + wki(1) <> 0 + 1 + 2 + 3 + 4 + 5 + 6 Then
   Exit Function
 End If

 wkT = _
  Format(wki(7), "0") & _
  Format(wki(6), "0") & _
  Format(wki(5), "0") & _
  Format(wki(4), "0") & _
  Format(wki(3), "0") & _
  Format(wki(2), "0") & _
  Format(wki(1), "0")

 If InStr(wkT, "0") = 0 Then Exit Function
 If InStr(wkT, "1") = 0 Then Exit Function
 If InStr(wkT, "2") = 0 Then Exit Function
 If InStr(wkT, "3") = 0 Then Exit Function
 If InStr(wkT, "4") = 0 Then Exit Function
 If InStr(wkT, "5") = 0 Then Exit Function
 If InStr(wkT, "6") = 0 Then Exit Function

 Get7Code = wkT
End Function

投稿日時 - 2018-12-15 11:40:03

お礼

度重ねてコードのご教示ありがとうございます。
この方法は、no1さんの方法と似ていますね。それでは、重複数字があればその組わせは除く点が異なります。現在この方法でやっています。
それからno8さんへのお礼も見て頂けると幸いです。
追加
ただ期待の文字列かは、0+1+2+3+4+5+6ではだめで、全ての文字列がそろっているかになるはずです。

投稿日時 - 2018-12-15 21:39:52

ANo.6

速度が問題になるのであれば、数列と番号の対応をとるのではなく、数列をそのまま数値として使用してはいかがでしょうか?
数列の長さが7であれば800万個の配列を用意すれば全て収まります。
(厳密には7,654,321個で十分ですが)
今のPCなら、整数800万個のデータを保持するだけのメモリは余裕で持っています。1データ4バイトとしても、32MB程度ですから。

投稿日時 - 2018-12-14 17:33:33

補足

この方法も速度改善のために少し考えましたが、
実は800万個なりの配列は一つだけではなく、数十万個必要なことに気が付きました。メモリはオーバしてしまい、切り詰めてもテーブルサイズの上限は数万程度のようです。

投稿日時 - 2018-12-15 21:46:40

お礼

ご返事ありがとうございます
その通りで非常に簡明になるので悩んでいるときはそれも考えましたが、最終的には同じPC上ではあるが、多分メモリ制約の多いインタープリタ言語のプラットフォームで処理せねばならないので、いかにも無駄のある処理には踏み切れておりません。
現在はNO1さんの簡明な方法でコーディングして進めています。しかし検証が進み速度の向上の必要性の段階になれば、その方法なども候補になるだろうと考えています。

投稿日時 - 2018-12-14 18:46:04

ANo.5

#4です。

> なにかうまく番号から数列を計算できないかが質問でした。

そうなるように作ったのに,わかってくれなくて悲しいです。

Sub main()
Dim k As Long
Dim n As Long
Dim np As Long, nt As Long, nt1 As Long
n = 4 '4個の文字列ならば4とする
ReDim nn(1 To n - 1) As Long
ReDim pp(1 To n) As Long
np = 24 '4個の文字列ならば4!=24とする
nt = 6 '左端の番号が7ならば1を引いて6とする
nt1 = np - 1 - nt
Call n2f(nt1, n, nn)
Call f2p(n, nn, pp) '右側の文字列が配列ppに戻される
'つまりpp(1)=1,pp(2)=2,pp(3)=4,pp(4)=3です。
Next
End Sub

やっていることは
左端の番号7から,まずnt1=17を求めておきます。
次にnt1からnnを求めます。
nn(i)は17=3!*(2)+2!*(2)+1!*(1)だからnn(1)=2,nn(2)=2,nn(3)=1です。
ここでn=4のときは3!から初めて,一般には(n-1)!から始めます。
次はnnからppを求めます。ppの初期値は
pp(1)=4,pp(2)=3,pp(3)=2,pp(4)=1としておきます。
nn(1)=2ですからppの後ろから1個目から合計3個に注目して
pp(1)=4,pp(2)=2,pp(3)=1,pp(4)=3
というように配列の内容をずらします。
一般にはnn(i)のときはppの後ろからi個目から合計nn(i)+1個に注目して配列の内容をずらします。nn(1)=2,nn(2)=2,nn(3)=1ならば,順に
pp(1)=4,pp(2)=3,pp(3)=2,pp(4)=1
pp(1)=4,pp(2)=2,pp(3)=1,pp(4)=3
pp(1)=2,pp(2)=1,pp(3)=4,pp(4)=3
pp(1)=1,pp(2)=2,pp(3)=4,pp(4)=3
となります。

投稿日時 - 2018-12-14 15:58:39

お礼

目的通り作っていただいたのに、理解できず済みませんでした。
動作説明まで書いていただいたので、今はまだ理解できかねますが、FORTRANに書き直しながら試してみます。高速化に有用かも知れないのでやってみたいと思います。
ありがとうございました。

投稿日時 - 2018-12-14 17:18:24

ANo.4

エクセルVBAで書いてみました。
main関数でn = 4としているところを適当に変えてください。
またmain関数でFor nt = 0 To np - 1のようにループさせていますが,これは検証のために全ケースで計算しているためです。ループさせずに1つだけでも動作します。
書き出しは
Range("A1").Offset(nt).Resize(, n - 1) = nn
Range("A1").Offset(nt, n).Resize(, n) = pp
の2つがありますが,必要なのはppの方だけでしょう。

Sub n2f(nt1 As Long, n As Long, nn() As Long)
For i = 1 To n - 1
nn(i) = 0
Next
k = 1
Do
k = k + 1
nn(n - k + 1) = nt1 Mod k
nt1 = Int(nt1 / k)
Loop While nt1 > 0
End Sub

Sub f2p(n As Long, nn() As Long, pp() As Long)
For i = 1 To n
pp(n + 1 - i) = i
Next
k = n - 1
k2 = n - 1
For i = 1 To k
j = nn(i)
t = pp(k2 + 1 - j)
For j2 = k2 + 1 - j To k2
pp(j2) = pp(j2 + 1)
Next
pp(k2 + 1) = t
k2 = k2 - 1
Next
End Sub

Sub main()
Dim k As Long
Dim n As Long
Dim np As Long, nt As Long, nt1 As Long
n = 4
ReDim nn(1 To n - 1) As Long
ReDim pp(1 To n) As Long
np = WorksheetFunction.Permut(n, n)
For nt = 0 To np - 1
nt1 = np - 1 - nt
Call n2f(nt1, n, nn)
Range("A1").Offset(nt).Resize(, n - 1) = nn
Call f2p(n, nn, pp)
Range("A1").Offset(nt, n).Resize(, n) = pp
Next
End Sub

投稿日時 - 2018-12-14 12:06:25

お礼

ごへんじありがとうございます。皆様のご説明に対してのご返事の一部は、no3さんへのお礼で述べておりますので、ご参照いただければ幸いです。
vbaならば、なんとか読めそうですが、残念ながらすぐには理解できそうにありません。質問でコードをご教示を願うような文面で申し訳ありませんでしたが、やはりコードよりno1さん、NO3さんのような手順説明がわかりやすかったですね。済みませんでした。

投稿日時 - 2018-12-14 13:36:06

ANo.3

> N個の処理を使ってn+1個の処理の形式で大分頭を悩ませましたが、ギブアップ気味です(まだ1日程度ですが)。

n=2の時は

12
21

の2通り。

n=3の時は

12のどこかに3を挿入する。場所の候補は
(a)1(b)2(c)
の(a)から(c)までの3カ所
21についても同様なので、2×3=6通り。

n=4ならn=3の時の結果から、長さ3文字に1文字挿入(4通り)、候補文字列が6つあるので4×6=24通り。

以下、同様に考えていけばいいのでは?

投稿日時 - 2018-12-14 11:49:53

お礼

ご返事ありがとうございます。
そうですね、質問の最初の文字列はこの考えをもとにしました。
ただ、皆さまのご説明がそうなのですが、質問の趣旨は数列を生成することではないのです。
生成した数列に番号を割りあて後、その番号に対応した数列を求めたいのです。生成した数列は上記の考えで並べたつもりなので、なにかうまく番号から数列を計算できないかが質問でした。

その後色々考えますと、どのような方法でも、求めたいことは難しいのではと考えています。
それで、今はいずれかの方法で数列を生成し、テーブルに並べ、そのテーブルを検索する方法でコードしています。
そもそもやっていることは、ある事象がN個の数列パターンであらわされ、その出現頻度を計算することなので、そのパターンを1個の数値で表し、その数値の頻度を集計するようにしています。
この計算の検証のため、その数値から逆にものとの数列パターンを導きたいのが今回の質問でした。
結局前記の通り、満足するすべての数列をふくむテーブルを作り、これを検索する方法で進めています。
この方法だと計算時間がかかるため、できうれば、数列と番号の関係がテーブル検索なしに計算できればよいのですが、それは困難と思ったのですが。。。。良い方法があるでしょうか。テーブルのサイズも問題になります。

投稿日時 - 2018-12-14 13:15:33

ANo.2

前、powershellで作ったのを貼っておきます。
nPn 7 で
5040個生成します。
functionnPn( [int64]$N ){
filterplaceN( $N ){
$ary=$_ -split ","
0..($N-1)|%{
$newarray=@()
$index=$_
0..($ary.length)|%{
if( $index -eq $_ ){
$newarray+=,$N
}
if ( $ary[$_] ){
$newarray+=$ary[$_]
}
}
$newarray -join ","
}
}

if ( $N -eq 0 ){ return $null }
if ( $N -eq 1 ){ return @(1) }
nPn ( $N - 1 )|placeN $N
}

投稿日時 - 2018-12-14 09:59:18

お礼

ご返事ありがとうございます。POWERSHELLでもこんなことができるのですか。これは再帰が入っているのでしょうか残念ながら読めませんでした。

投稿日時 - 2018-12-14 13:19:40

ANo.1

a=1から7までループ
b=1から7までループ
c=1から7までループ
d=1から7までループ
e=1から7までループ
f=1から7までループ
g=1から7までループ

a=b or a=c or a=d or a=e or a=f or a=g or
b=a or b=c or b=d or b=e or b=f or b=g or
c=b or c=a or c=d or c=e or c=f or c=g or
d=b or d=c or d=a or d=e or d=f or d=g or
e=b or e=c or e=d or e=a or e=f or e=g or
f=b or f=c or f=d or f=e or f=a or f=g or
g=b or g=c or g=d or g=e or g=f or g=a

でないとき aからgまで書き出す。

こういうことかな?

投稿日時 - 2018-12-13 18:55:15

お礼

ご返事ありがとうございます。
この端的な方法によると右側の文字列(ただし予定の順と異なりますが)が生成できることがわかります。その出現順に番号を振り、毎回このループを実行して、該当番号で生成した文字列が目的の文字列になることがわかりました。
ただこの方法では毎回ループを実行せねばならないところが多少残念ですが。
本来目論んだことは、該当番号から直接対応文字列を生成することなのですが、実用的には少々工夫が必要です。

投稿日時 - 2018-12-13 21:12:40

あなたにオススメの質問