13
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ Do you need them to be in the same order? $\endgroup$
    – rm -rf ♦
    Sep 21, 2013 at 4:01
  • $\begingroup$ yes. I need them to be in same order $\endgroup$
    – Vajira
    Sep 21, 2013 at 4:55
  • 2
    $\begingroup$ 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. $\endgroup$
    – Mr.Wizard
    Sep 21, 2013 at 13:16
  • 1
    $\begingroup$ @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. $\endgroup$
    – Michael E2
    Sep 21, 2013 at 19:52
  • 1
    $\begingroup$ @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. $\endgroup$
    – Michael E2
    Sep 21, 2013 at 20:26

5 Answers 5

Reset to default
6
$\begingroup$

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).

Improve this answer
$\endgroup$
0
12
$\begingroup$

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
Improve this answer
$\endgroup$
11
$\begingroup$ 
FixedPoint[
      StringReplace[#, a___ ~~ x_ ~~ b___ ~~ x_ ~~ c___ :> a ~~ x ~~ b ~~ c] &, "13233454766"]

1324576

Improve this answer
$\endgroup$
1
  • $\begingroup$ Regex version: FixedPoint[StringReplace[#, RegularExpression["(\\d)(.*)(\\1)"] -> "$1$2"] &, str]. $\endgroup$
    – J. M.'s eventual burnout ♦
    Mar 13, 2016 at 8:20
2
$\begingroup$ 
"" <> (Characters@ "113233454766" //. {a___, x_, b___, x_, c___} :> {a, x, b, c})

(* "1324576" *)
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The OP wrote "without converting the string to a list" and Charactersdoes exactly that :) $\endgroup$
    – Dr. belisarius
    Sep 21, 2013 at 12:20
  • 1
    $\begingroup$ @belisarius I didn't notice that before :) $\endgroup$
    – chyanog
    Sep 21, 2013 at 13:03
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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