Transform string from a1b2c3d4 to abcd1234

Question

I am given a string which has numbers and letters.Numbers occupy all odd positions and letters even positions.I need to transform this string such that all letters move to front of array,and all numbers at the end.

The relative order of the letters and numbers needs to be preserved

I need to do this in O(n) time and O(1) space.

eg: a1b2c3d4 -> abcd1234 , x3y4z6 -> xyz346

This previous question has an explanation algorithm, but no matter how hard i try,i cant get a hold of it.

I hope someone can explain me this with a example test case .

This is a classic _array of structures_ to _structure of arrays_ problem. Try looking up transpose operation. — legends2k, Jun 19 '13 at 18:17
The difficult part here is the `O(1)` space. I think that you can do a for loop from 0 to n/2 and perform some switches. — Arnaud Denoyelle, Jun 19 '13 at 18:21
There are two different ways to solve this: 1. in-place stable counting sort, and 2. in-place matrix transposition. — Evgeny Kluev, Jun 19 '13 at 18:24
For example, if your array has a size of 10, you will switch elements 0 and 5, 2 and 7, 3 and 8, 4 and 9. This gives you the shape of the for loop. — Arnaud Denoyelle, Jun 19 '13 at 18:25
Does the operation need to work in-place, or is `O(1)` space good enough? (Why not create a data structure of the same size?) — Daniel, Jun 19 '13 at 19:03
does the array always have an equal ammount of numbers and letters? — Sam I am says Reinstate Monica, Jun 19 '13 at 19:07
@Spandan I've just made an edit to my answer. it has a very simple solution, you should check it out — Sam I am says Reinstate Monica, Jun 19 '13 at 19:18
possible duplicate of [in-place permutation of a array follows this rule](http://stackoverflow.com/questions/3062974/in-place-permutation-of-a-array-follows-this-rule) — zw324, Jun 19 '13 at 20:05

jason · Accepted Answer · 2013-06-19T18:39:33.257

9

The key is to think of the input array as a matrix like this:

a 1
b 2
c 3
d 4

and realize that you want the transpose of this matrix

a b c d
1 2 3 4

Remember, multi-dimensional arrays are really just single-dimensional arrays in disguise so you can do this. But you need to do this in-place to satisfy the O(1) space requirement. Fortunately, this is a well-known problem complete with several possible approaches.

edited Jun 19 '13 at 18:39

answered Jun 19 '13 at 18:27

jason

236,483
35
423
525

1

Is there a O(1) space algorithm on the linked website? – zw324 Jun 19 '13 at 18:31
Non-square matrices: Following the cycles ... In order to determine whether a given cycle has been moved already, the simplest scheme would be to use O(MN) auxiliary storage, one bit per element, to indicate whether a given element has been moved. To use only O(M+N) or even O(log MN) auxiliary storage, more complicated algorithms are required, and the known algorithms have a worst-case linearithmic computational cost of O(MN log MN) at best, as first proved by Knuth (Fich et al., 1995; Gustavson & Swirszcz, 2007). – zw324 Jun 19 '13 at 18:32
Okay, will delete that. Please understand watching a post grew old without valid reference is painful, no offense meant. – zw324 Jun 19 '13 at 18:44
@Jason:"It doesnt work like that" ?..First of all,i mentioned in my question pretty friggin clearly,that i have an algorithm,but m having hard time to understand what it does,so i need a dry run...if you have a corect algo,which i dont think you do,then post a example,else like ziyao said,"Knock knock knock" .get it! – Spandan Jun 19 '13 at 18:46
2

@Spandan: You're rapidly losing my sympathy. I already explained to you how to approach the problem and even provided links to an implementation. I'm not going to hold your hand. – jason Jun 19 '13 at 18:49
1

@Ziyao Wei: It's fine, thanks for correcting. One of the things that I think people love the most about the Stack Overflow community is that we generally interact at a pretty respectful level; the community is great at self-policing away non-constructive behavior. We nerds are ruthless at tearing apart each other's ideas until we collectively hit upon the right one, but it's done in a way here without degenerating into awful behavior like on many other Q&A sites. – jason Jun 19 '13 at 18:51
@Jason: with all due respect, you didn't mention the time/space complexity of the solutions you referred to. So just the pointing onto a bunch of complicated algorithms which maybe fit to the original question without even choosing an appropriate one isn't a perfect answer, is it? – Vlad Jun 19 '13 at 18:53
@Vlad: Directly from my [last link](http://rosettacode.org/wiki/Matrix_transposition#C): "*Transpose a matrix of size `w x h` in place with only `O(1)` space and without moving any element more than once.*" To be clear, I initially pasted the wrong link when I first answered, and I do apologize for that. – jason Jun 19 '13 at 18:57
@Ziyao Wei: Also, note that the quote referencing space that you post applies to "[determining] if a cycle has been moved already." That is *not* strictly necessary for correctness of the algorithm. That is only done to accelerate the algorithm. That is, extra space is consumed to accelerate the time needed to complete the transposition; it's the classic [space-time tradeoff](https://en.wikipedia.org/wiki/Space–time_tradeoff) but it's not strictly necessary. We can follow the same algorithm, without worrying about repeating a cycle and achieve the `O(1)` space requirement. – jason Jun 19 '13 at 19:08
Well, but I don't see why the solution you referred to is `O(n)` in time. It's true that it moves each element only once, but it uses non-constant time at each iteration by `start` for finding if the current `start` is the minimal value in some transposition cycle. So I suspect it's indeed quadratic in time. – Vlad Jun 19 '13 at 20:02
@Vlad I agree the solution is not trivially O(n), although a good read. However, I did some benchmarking and cannot find any quadratic behavior, so I suspect it is either linear or O(nlogn). Anyway, http://stackoverflow.com/questions/3062974/in-place-permutation-of-a-array-follows-this-rule/3063647#3063647 seems to be a clearer solution. – zw324 Jun 19 '13 at 20:05

Transform string from a1b2c3d4 to abcd1234

1 Answers1