Not Yet Answered # Algorithm for string combinations

sarehu 84 Discussion Starter casperguru sarehu 84 Write a C program that should create a 10 element array of random integers (0 to 9). The program should total all of the numbers in the odd positions of the array and compare them with the total of the numbers in the even positions of the array and indicate ...

0

Given *k* identical cats and *n* scratching posts in a line, devise an algorithm for finding all the unique ways to arrange the cats about the scratching posts. There should be (n + k)!/((n+k)!n!) ways to do so (i.e. "n+k choose k"). So, given that your given string has *k* instances of some particular character, remove those characters from the string, find the possible combinations of rearrangement, and then add the characters to the string in all the possible ways.

That's one way of looking at it. Another way is to use the standard recursive permutation generator with a slight tweak to avoid equivalent subcases that arise due to equal characters.

0

Yea it seems like a decent solution but I am a bit concerned about the complexity of this solution.

1. Finding k instances of some particular character

Assuming that you sort the string based on the ascii characters and then remove all the duplicates and store is in some array.(Time complexity O(nlogn)

space complexity O(no. of duplicate characters) + any extra complexity for the sort operation(tweaking quick sort might remove this one) but still quite a bit of overhead.

2.Rearranging all the letters O(n^2)

3.Putting the repeated characters in the placeholders O(n^2*(num of repeated characters*(length of the string-1)))

So the complexity seems to be pretty high both in terms of time and space.

Can anyone think of an in place algorithm for this?

0

You can do a typical recursive approach at a small cost per permutation you output, if you reuse the previous permutation, so I don't see what the problem is. I don't know what you mean by "rearranging all the letters." The number of permutations you need to generate is n! for general permutations, and (n!)/((s!)^(n/s)) in the worst case when there are s different characters. Both of these are worse than exponential.

I don't see why you'd care about an in place algorithm here; there is no benefit when the memory usage is exponentially small compared to the running time.

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

Hi. so this is actually a continuation from another question of mineHere but i was advised to start a new thread as the original question was already answered.

This is the result of previous question answered :

code for the listbox - datagridview interaction

At the top of the code ...

the function that I created to find the ...