0

このページでこのインタビューの質問に出くわしました: (http://newworld-alex.blogspot.com/2009/03/facebook-interviewzz.html)

技術的な質問: Python で、ある単語の文字バリエーションの辞書が与えられた場合、たとえば dictChars = {"e" : [E, 3], "x" : [X], "a" : [A, @], "m " : [M]}パスワード クラッカーのような部分的な文字列順列ジェネレータを実装します。つまり、exaM、exAm、exAM、ex@m、... を生成します。Python で単純な 3 行の再帰ソリューションを実装しました。

私はPythonで解決策を持っていますが、彼のように3行にする方法がわかりません。

参考までに、これが私の現在の解決策です：

def allPossiblePasswords(password, mapping):
   if len(password) == 0:
      return [""]
   else:
      next = allPossiblePasswords(password[1:], mapping)
      if password[0] in mapping:
         return [c + n for c in mapping[password[0]] for n in next]
      else:
         return [password[0] + n for n in next]

前もって感謝します！

4

4 に答える 4

3

自己剽窃はカウントされませんよね？

import itertools

def all_possibles(password, mapping):
    char_options = ([char]+mapping.get(char,[]) for char in password)
    for poss in itertools.product(*char_options):
        yield ''.join(poss)

これは、1 行のバリアントであっても、好きなだけコンパクトにすることができます。

possibles = lambda p,m: map(''.join, itertools.product(*([c]+m.get(c,[]) for c in p)))

編集：ああ。再帰が必要であることに気づきませんでした。その場合は、次のようにします。

def all_recur(password, mapping):
    return [''] if not password else [c + n for c in [password[0]] + mapping.get(password[0], []) for n in all_recur(password[1:], mapping)]

これは基本的にあなたの圧縮バージョンです。これらは両方とも 'exam' (つまり、変更されていないパスワード) も返すことに注意してください。それが欲しかったのかどうかはわかりません。

于 2012-04-10T01:57:47.013 に答える
1

これは多くの点で間違っています。でも一応投稿してます。要求どおり、これは再帰的なソリューションです。

>>> def pw_vars(in_word, out_word, equivs):
...     if not in_word: return [out_word]
...     return sum((pw_vars(in_word[1:], out_word + c, equivs) for c in [in_word[0]] + equivs[in_word[0]]), [])
... 
>>> pw_vars('foo', '', {'f':['F', '='], 'o':['0', 'O']})
['foo', 'fo0', 'foO', 'f0o', 'f00', 'f0O', 'fOo', 'fO0', 'fOO', 'Foo', 'Fo0', 
 'FoO', 'F0o', 'F00', 'F0O', 'FOo', 'FO0', 'FOO', '=oo', '=o0', '=oO', '=0o', 
 '=00', '=0O', '=Oo', '=O0', '=OO']

実際にこれを行うべきではないと言う必要がないことを願っています. その人は実際にこの仕事に就いたのですか？私は懐疑的です。

実際には、DSM のバージョンの方が優れていることに気付きましたが、ほとんど許容範囲です! これが私のバージョンの DSM のバージョンです。これは、以下の Mark Ransom のポイントも満たしています。

>>> def pw_vars(pw, equivs):
...     if not pw: return ('',)
...     return (c + var for c in [pw[0]] + equivs.get(pw[0]) for var in pw_vars(pw[1:], equivs))
... 
>>> list(pw_vars('foo', {'f':['F', '='], 'o':['0', 'O']}))
['foo', 'fo0', 'foO', 'f0o', 'f00', 'f0O', 'fOo', 'fO0', 'fOO', 'Foo', 'Fo0', 'FoO', 'F0o', 'F00', 'F0O', 'FOo', 'FO0', 'FOO', '=oo', '=o0', '=oO', '=0o', '=00', '=0O', '=Oo', '=O0', '=OO']
于 2012-04-10T02:15:07.973 に答える
1 
mapping = {'a': ['A', '@'], 'x': ['X'], 'e': ['E', 3], 'm': ['M']}

password = "exam"

from itertools import product
allPossible = list(product(*([letter] + mapping[letter] for letter in password)))
于 2012-04-10T01:55:50.007 に答える
0 
equivs = dict(e=['E', '3'], x=['X'], a=['A', '@'], m=['M'])

def gen(c, *cs):
    if cs: return (x + y for x in [c] + equivs.get(c, []) for y in gen(*cs))
    else: return [c] + equivs.get(c, [])

for each in gen(*'erxuam'):
    print each
于 2012-04-10T05:00:39.233 に答える