Q&A
何個選ぶ組み合わせですか?00など重複ありですか?
お世話になります。
ふと気になったので、ご質問させて頂きます。
言語は問わないのですが、アルゴリズムをご教示頂けますと幸いです。
0123456789abcdefghijklmnopqrstuvwxyz
上記の文字列から全通りの組み合わせを配列にするためには、
どのようなアルゴリズムがありますでしょうか？
現実的に、
計算すると動作が固まってしまいますか？
ozwk様、お世話になります。全ての重複も含む本当の意味での全通りは、計算不可能でしょうか？
やってほしいことだけ記述している上に、仕様が明確ではないです。質問を整理してください。
いや、何が「本当の意味」なんですか?
アルゴリズムを考える時でも質問する時でも一緒なんですが、紙と鉛筆で解けるぐらいまで問題を小さくして、具体的な例で取り扱ったらいいと思います。例えば問題が abc だとしたら、欲しい出力は何ですか?
重複ありの場合、「0を無限に選び続ける」ようなパターンを含むのであれば、当然ながらパターン数も無限になります。どのようなパターンが許されるのか、もっと詳しく定義してください。
回答6件
0
まず、全パターンは、各文字について「入れるか入れないか」2通りなので、36文字についてそれを行えば、2の36乗通り（687
億通り）となります。
あとは、0から2の36乗-1までを順番に作っていって、各ビットが立っているかを文字の有無に対応付ければいいでしょう。
投稿2018/01/12 00:44
総合スコア145186
なお、これは重複しないことが前提です。
ご回答有難うございました。
> 各文字について「入れるか入れないか」2通りなので、36文字についてそれを行えば、2の36乗通り（687億通り）
36bitの組み合わせは確かにその通りなのですが、そのアルゴリズムは「順不同」なので、"34" と "43" が合わせて1通りという扱いになってしまうのではありませんか。
「組み合わせ」と取ったのでこういう回答なんだと思いますよ。
なるほど、「重複しない0～36文字の組み合わせ」と受け取るのであれば、その通りですね。
0
ベストアンサー
36個（数字10＋英字26）の順列組み合わせなら、その総数は 36! 個になります。
約 3.72 * 10^41 ですね。
現実的に全部出力しようとしたらとんでもないことになりますね。
毎秒1兆個（=10^12）の順列を出力できたとしても、3.72 × 10^29 秒。１日は 8.64 * 10^4 秒ですから、ざっくり 4.305 × 10^24 日。1年はざっくり 365.25 日として、
1.1787 × 10^22 年かかります。
宇宙の年齢が多く見積もっても 140億年（=1.4×10^10）ですから、宇宙開闢以来やってたとしても全然終わりが見えませんね。
投稿2018/01/12 00:50
総合スコア13703
0
解決済になってしまいましたけど、「無限の組み合わせ」というのでこんなネタを、、配列風にしてみました笑
言語はpython3です。pythonの場合正確にはリスト風ですけども。
python
1from random import randint 2 3class randomStr(object): 4 def __init__(self,n): 5 self._n = n 6 7 def __getitem__(self,_): 8 strKinds = '0123456789abcdefghijklmnopqrstuvwxyz' 9 result = '' 10 while randint(0,self._n) != 0: 11 result += strKinds[randint(0,35)] 12 13 return result 14 15if __name__=='__main__': 16 arr = randomStr(10) # 毎回1/11の確率で連続が終了 17 print(arr[5]) 18 print(arr[114514])
出力例
uqiz2w6dwk8zyrxl57m0d7y i9sthvbtws021w6zi08gkftm
くだらないですね。ただのネタです。
テキトーなアカウント名生成するのには使えるかも…？
まぁ添字でアクセスするたびに結果が変わるので配列とは絶対に言えませんね。
投稿2018/01/12 01:28
編集2018/01/12 01:43
総合スコア2043
0
勝手なこと蛇足ですが、この文章の質問で、パスワードの問題だ文字数指定しろよ。と理解できるのすごい。
僕は36文字の順列組み合わせだと読んで（36!だな）と思ってしまった。
よく読めば、レインボーテーブルの構築の概算を知りたいのかも、とわかったかも。
未来の技術は、結果を保存より高速に解を見つけ出すようですよ。
投稿2018/01/17 02:44
総合スコア56
文字数不定で重複可なので 36! にはなりません。
質問者の質問に対する回答、ではなく個人の感想のようなので評価を下げさせていただきました
特定の方の回答について何かおっしゃりたいことや疑問があれば、そちらのコメント欄にて議論すべきと思います
評価を下げるのに理由はいりません。そんなご丁寧に。
特定の誰か向けでなく、あえて言えば質問向けにと投稿したので、
新たな回答にしました。僕が言いたいことは上に書いたことです。
誰かを揶揄してるように読めたらすみません。
僕はtakitoさんが、僕が特定の方の回答に一言あると思った理由と、
その内容を知りたいです。
あるとすれば、質問は拙いなら、その人は初心者なんだろうし、
質問者の知りたいことを解決できるような議論になればと思いました。
いま読み返せば、組み合わせのアルゴリズムを質問しているので、
文字列を降順に並べて昇順にバブルソート。という答えかも。
質問者がバカにされる質問ってなんだよ。
くどい言い方になりますが、解決済みなので解決しているはずです。
議論は不要でしょう。
あなたの回答
tips
プレビュー
