-2

Inspired by the suggestion Recursive implementation of permutations in Python to use a set to avoid duplicated for permutations in a string, I was thinking of using a set as a general method to remove duplicated from a string (obviously order won't be preserved).

So If I have

str1 = 'Thiss'
set_str1 = set(str1)
print set_str1

Output set(['T','h', 'i', 's'])

The question is how to get the string back from this set. I was thinking that I can just use set and then convert it back to a string and then find permutations of the modified string. Is that an efficient way to go about it? Also I don't want to use itertools because I am just preparing for some interviews.

Community
  • 1
  • 1
vkaul11
  • 4,098
  • 12
  • 47
  • 79
  • I don't understand: do you want to preserve order or not? If you do `"".join(set_str1)` you will join the set into a string, but it might not be in the same order, so you're not getting "the string back" as you're asking. – David Robinson Jul 18 '13 at 18:15
  • 1
    If you are going to find permutations of the string, then you don't need to turn it back; just treat the set as the sequence from which to generate permutations. – Martijn Pieters Jul 18 '13 at 18:16
  • So you would wan't `"Thsiss"` to become `"Thsi"`, correct? – arshajii Jul 18 '13 at 18:16
  • Possible dupe of http://stackoverflow.com/questions/9841303/best-way-to-remove-duplicate-characters-from-a-string – woozyking Jul 18 '13 at 18:17
  • No for permutations, I don't want to preserve order David. Martijn, the permutation output should be a list of strings. So I should just use join statement to create strings from elements of a set? – vkaul11 Jul 18 '13 at 18:18

2 Answers2

3

Since, sets don't preserve order, you may/may not get the original string back, but you can get a string of the elements using join(). Like follows - 

>>> "".join(set(['T','h', 'i', 's']))
'ihsT'

Then, you can use itertools.permutations to find the permutations.

>>> list(permutations("".join(set("Thisss"))))
[('i', 'h', 's', 'T'), ('i', 'h', 'T', 's'), ('i', 's', 'h', 'T'), ('i', 's', 'T', 'h'),
  ... ]

Then, similarly apply join to get the elements in string format from the permutations list.

You don't need to join the set to get the permutations though.

Just doing 

>>> list(permutations(set("Thisss")))

Gives similar answer, and then you can join the elements.

Sukrit Kalra
  • 33,167
  • 7
  • 69
  • 71
1

You do not need to recreate the string; sets do not have a set ordering anyway, and a set suffices to create permutations:

>>> for p in permutations(set('Thiss')):
...     print(''.join(p))
... 
Tsih
Tshi
Tish
Tihs
Thsi
This
sTih
sThi
siTh
sihT
shTi
shiT
iTsh
iThs
isTh
ishT
ihTs
ihsT
hTsi
hTis
hsTi
hsiT
hiTs
hisT
Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
  • Thanks Martijn, I wanted to do it without itertools but I think your answer still makes sense. – vkaul11 Jul 18 '13 at 18:22
  • I suppose I should apply my permutation program on the set even if I don't use the itertools and finally convert to list of strings. Isn't it inconvenient to do it in sets given that we cannot reference sets using an index so I cannot use recursion on elements of the set. Perhaps I should convert the set to a list and write the permutation? – vkaul11 Jul 18 '13 at 18:29
  • If your algorithm requires indexing, then by all means convert the set to a list, yes! – Martijn Pieters Jul 18 '13 at 18:33
  • If I use an algorithm without indexing using sets, then I will perhaps need to remove one element from a set to create a subset which may not be that inefficient either. – vkaul11 Jul 18 '13 at 18:36
  • FWIW, the [`itertools` documentation](http://docs.python.org/2/library/itertools.html#itertools.permutations) turns the iterable into a tuple too. – Martijn Pieters Jul 18 '13 at 18:45
  • Oh, ok so it is better to turn the set into a tuple instead of a list. – vkaul11 Jul 18 '13 at 18:57