Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

How do you remove duplicate characters in a string without converting the string to a list. I want to delete all duplicate characters in a string (i.e. get the unsorted union of characters). For example string like "113233454766" should give me string "1324576". Note order.

I tried this:

 StringReplace["113233454766", a___ ~~ x_ ~~ b___ ~~ x_ ~~ c___ :> a ~~ x ~~ b ~~ c]

But it won't give me answer. I think I'm not fully understand about pattern.

share|improve this question
1  
Do you need them to be in the same order? –  rm -rf Sep 21 '13 at 4:01
    
yes. I need them to be in same order –  Vajira Sep 21 '13 at 4:55
2  
Why do you not want to convert the String to a list of characters? Since it is probably the most natural approach, as your comment implicitly acknowledges, I think you should explain why you find it unacceptable. –  Mr.Wizard Sep 21 '13 at 13:16
1  
@Vajira See my answer for timings. Unless someone finds a fast way of deleting duplicates in a String, it looks like splitting to character codes then deleting is faster. –  Michael E2 Sep 21 '13 at 19:52
1  
@Vajira No, it's a good question, even if now you decide you want to do something else. You could ask another question, if it's sufficiently different. –  Michael E2 Sep 21 '13 at 20:26
show 7 more comments

5 Answers

up vote 6 down vote accepted

I'll add this one:

FromCharacterCode @ DeleteDuplicates @ ToCharacterCode @ "113233454766"

"1324576"


Comparison

First, @belisarius' and @IstvánZachar have the only solutions that do not convert the string to a list. So +1 for that. But they're somewhat to very slow. I'll use Beowulf as an example string:

text = ExampleData[{"Text", "BeowulfOldEnglish"}];

Timings:

István has one that is the same idea as mine, but it uses Characters instead of ToCharacterCode. The other one of his I include is the faster of the two that do not convert the string to a list.

SetAttributes[timeAvg, HoldFirst]
timeAvg[func_] := Do[If[# > 0.3, Return[#/5^i]] & @@ Timing@Do[func, {5^i}], {i, 0, 15}]

FromCharacterCode@DeleteDuplicates@ToCharacterCode@text // timeAvg  (* Michael E2)
StringJoin@DeleteDuplicates@Characters@text // timeAvg              (* Istvan's fastest *)
Block[{f}, f[x_] := (f[x] = ""; x);                                 (* Istvan's String *)
  StringReplace[text, x_ :> f@x]] // timeAvg
FixedPoint[                                                         (* belisarius *)
  StringReplace[#, a___ ~~ x_ ~~ b___ ~~ x_ ~~ c___ :> a ~~ x ~~ b ~~ c] &,
  text] // timeAvg

0.00130796
0.0344223
0.090330
56.499878

Memory:

ByteCount@text
ByteCount@ToCharacterCode@text
ByteCount@Characters@text

124528
900312
5401088

One can see that ToCharacterCode uses roughly eight times the memory. (It converts the string to packed array.) Characters is very wasteful of memory, using roughly 45 times the amount as String.

On the other hand, if I start from a fresh kernel, MaxMemoryUsed[] returns about 56MB. We can compare how much memory is used by evaluating MaxMemoryUsed[] after running a method. For this test, I joined 100 copies of Beowulf. Mine used 241MB and for István's used 629MB. For @belisarius' it was about 113MB when I aborted it as it would take too long to run to completion.

Test code (substitute a desired method for the third line):

text2 = StringJoin[Table[#, {i, 100}] &@ ExampleData[{"Text", "BeowulfOldEnglish"}]];
MaxMemoryUsed[]
FromCharacterCode@DeleteDuplicates@ToCharacterCode@text2;
MaxMemoryUsed[]

If eight times greater is too much, you might consider splitting the string, deleting duplicates in each pieces, combining the results, and deleting again.

From a comment by the OP, it seems there are lots of strings, and perhaps the longest string may not be overly large. If so, then the strings may be processed separately (and in parallel, as desired).

share|improve this answer
add comment
FixedPoint[
      StringReplace[#, a___ ~~ x_ ~~ b___ ~~ x_ ~~ c___ :> a ~~ x ~~ b ~~ c] &, "13233454766"]

1324576

share|improve this answer
add comment

Some other methods, without using the string patternmatcher (i.e. converting string to list):

s = Characters@"113233454766";
StringJoin @@ (First /@ Tally@s)
StringJoin@DeleteDuplicates@s
StringJoin@Block[{f}, f[y_] := (f[y] = Sequence[]; y); f /@ s]

Similar as the last one with the string patternmatcher (without converting to list):

Block[{f}, StringReplace[s, {x_ :> If[TrueQ@f@x, "", f@x = True; x]}]]
Block[{f}, f[x_] := (f[x] = ""; x); StringReplace[s, x_ :> f@x]]

They all return:

1324576
share|improve this answer
add comment
"" <> (Characters@ "113233454766" //. {a___, x_, b___, x_, c___} :> {a, x, b, c})

(* "1324576" *)
share|improve this answer
1  
The OP wrote "without converting the string to a list" and Charactersdoes exactly that :) –  belisarius Sep 21 '13 at 12:20
1  
@belisarius I didn't notice that before :) –  chyaong Sep 21 '13 at 13:03
add comment

Just another way to do it without converting the string to a list. You have to define the character range.

rest[x_ /; x == {}] := {}
rest[x_] := Rest[x]

str = "113233454766";
(str = StringReplacePart[str, "", rest@StringPosition[str, #]]) & /@ CharacterRange["1", "9"];
str

"1324576"

When I tried this with Michael E2's test, not being able to find the full character range though, it came in at 72 seconds. Had I found the full character range it would have been slower, but then again the full character range of a typical text is not the same as old English.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.