Найти всю возможную комбинацию строки без изменения порядка [duplicate]
Короче говоря, объекты Java обладают некоторыми очень своеобразными свойствами.
В общем, Java имеет примитивные типы (int, bool, char, double и т. д.), которые передаются непосредственно по значению. Тогда у Java есть объекты (все, что происходит от java.lang.Object). Объекты на самом деле всегда обрабатываются посредством ссылки (ссылка является указателем, который вы не можете коснуться). Это означает, что по сути объекты передаются по ссылке, так как ссылки обычно не интересны. Тем не менее, это означает, что вы не можете изменить, на какой объект указывается, поскольку сама ссылка передается по значению.
Звучит ли это странно и запутанно? Рассмотрим, как C реализует передачу по ссылке и передает значение. В C по умолчанию принято передать значение. void foo(int x) передает значение int по значению. void foo(int *x) - это функция, которая не хочет int a, а указатель на int: foo(&a). Можно было бы использовать это с оператором & для передачи адреса переменной.
Возьмите это на C ++, и у нас есть ссылки. Ссылки в основном (в этом контексте) синтаксического сахара, которые скрывают указательную часть уравнения: void foo(int &x) вызывается foo(a), где сам компилятор знает, что это ссылка и адрес без ссылки a должен быть принят. В Java все переменные, относящиеся к объектам, фактически относятся к ссылочному типу, фактически вызывая вызов по ссылке для большинства целей и целей без мелкозернистого управления (и сложности), предоставляемого, например, C ++.
6 ответов
Вы слишком задумываетесь об этом
Эта часть пытается слишком много
for word in words:
for i in range(len(word)):
temp = string[0:i] + first + string[i:len(string)]
print "temp = " + str(temp)
perm.append(temp)
Посмотрите, насколько это просто должно быть
def get_powerset (string):
perm = []
if len(string) == 0:
perm.append("")
return perm
#if len(string) == 1:
# perm.append(string)
# perm.append("")
first = string[0]
print "first = " + str(first)
rem = string[1:len(string)]
print "rem = " + str(rem)
words = get_powerset(rem)
perm.extend(words)
for word in words:
perm.append(first+word)
return perm
if __name__=="__main__":
a = "ab"
mag = get_powerset(a)
print mag
Теперь вы сможете сделать код намного приятнее с небольшим рефакторингом
Пробовали ли вы отслеживать то, что на самом деле делает ваш алгоритм?
getperm('ab'):
first, rem = 'a', 'b'
words = getperm('b')
first, rem = 'b', ''
words = getperm('')
words = ['']
for word in words:
for i in range(len(word)):
pass # only called on '', so doesn't matter
return []
words = []
for word in words:
pass # only called on [], so doesn't matter
Итак, здесь нет нюансов Python; ваш алгоритм возвращает пустой список в O (N) шагах, и вы правильно закодировали этот алгоритм на Python.
(Вместо того, чтобы трассировать его вручную, вы можете добавить еще несколько полезных операторов печати и посмотрим, что делает каждый шаг.)
Вероятно, это был не тот алгоритм, который вам нужен, но вам нужно сообщить нам, что вы пытались делать. Вы, например, переносите некоторый псевдокод из Hoare в Python? Если да, то что такое псевдокод?
Реорганизованное итеративное решение без модуля itertools:
def powerset(s):
a = ['']
for i,c in enumerate(s):
for k in range(2**i):
a.append(a[k]+c)
return a
Это то, что вы хотите?
import itertools as it
def func(s):
for i in range(len(s)+1):
for combo in it.combinations(s,i):
yield "".join(combo)
print list(func("abc"))
-
1Я считаю, что это будет сделано, но я хочу реализовать решение, используя рекурсию. Спасибо! – mythander889 28 September 2012 в 02:39
-
2искал комбинации с заменой. Видел это, пошел к документам ..
combinations_with_replacement()- на самом деле метод там! : ') – Somjit 7 November 2015 в 07:32 -
3Есть ли способ сделать то, что вы делаете, не используя пакет itertools? – nakulchawla09 12 October 2016 в 07:42
Существует способ перестановок:
>>> import itertools
>>> chars = "ABCD"
>>> perms = list(itertools.permutations(chars))
>>> print(perms)
[('A', 'B', 'C'),
('A', 'C', 'B'),
('B', 'A', 'C'),
('B', 'C', 'A'),
('C', 'A', 'B'),
('C', 'B', 'A')]
-
1но он действительно не хочет перестановок, которые ему нужны для питания ... – Joran Beasley 28 September 2012 в 02:44
-
2Как он может кодировать алгоритм с неправильным именем? Подозрительно ... – Pedro Lacerda 28 September 2012 в 04:04
Используйте powerset из more_itertools :
>>> import more_itertools
>>> ["".join(p) for p in list(more_itertools.powerset("ab"))]
['', 'a', 'b', 'ab']
Это powerset - это функция удобства, непосредственно реализованная с помощью функции itertools рецепты .
.extendпросто загружает результат предыдущего уровня в текущий результат. – John La Rooy 28 September 2012 в 06:06[" ", "a", "b"], я думал о терминах получения вывода, например[" ", "a", "b", "ab", "ba"]– nakulchawla09 12 October 2016 в 23:36