iphone - Permutations/Anagrams in Objective-C -- I am missing something -

iphone - Permutations/Anagrams in Objective-C -- I am missing something -

(code below regarding question)

per this stack overflow question used pegolon's approach generating possible permutations of grouping of characters within nsstring. however, trying not generate anagram permutations of same length, possible combinations (any length) of characters in string.

would know how alter next code this? much like: generate permutations of lengths -- (for fear of them needing reply homework) did not leave code. have sample of thought @ bottom of post... did not.

so, code, is, generates the, teh, hte, het, eth , eht when given the. need along lines of: t,h,e,th,ht,te,he (etc) in add-on above 3 character combinations.

how alter this, please. (ps: there 2 methods in this. added allpermutationsarrayofstrings in order results strings, want them, not array of characters in array). assuming magic happen in pc_next_permutation anyway -- thought mention it.

in nsarray+permutation.h

#import <foundation/foundation.h> @interface nsarray(permutation) - (nsarray *)allpermutationsarrayofarrays; - (nsarray *)allpermutationsarrayofstrings; @end

in nsarray+permutation.m:

#define max_permutation_count 20000 nsinteger *pc_next_permutation(nsinteger *perm, const nsinteger size); nsinteger *pc_next_permutation(nsinteger *perm, const nsinteger size) { // slide downwards array looking we're smaller next guy nsinteger pos1; (pos1 = size - 1; perm[pos1] >= perm[pos1 + 1] && pos1 > -1; --pos1); // if doesn't occur, we've finished our permutations // array reversed: (1, 2, 3, 4) => (4, 3, 2, 1) if (pos1 == -1) homecoming null; assert(pos1 >= 0 && pos1 <= size); nsinteger pos2; // slide downwards array looking bigger number found before (pos2 = size; perm[pos2] <= perm[pos1] && pos2 > 0; --pos2); assert(pos2 >= 0 && pos2 <= size); // swap them nsinteger tmp = perm[pos1]; perm[pos1] = perm[pos2]; perm[pos2] = tmp; // reverse elements in between swapping ends (++pos1, pos2 = size; pos1 < pos2; ++pos1, --pos2) { assert(pos1 >= 0 && pos1 <= size); assert(pos2 >= 0 && pos2 <= size); tmp = perm[pos1]; perm[pos1] = perm[pos2]; perm[pos2] = tmp; } homecoming perm; } @implementation nsarray(permutation) - (nsarray *)allpermutationsarrayofarrays { nsinteger size = [self count]; nsinteger *perm = malloc(size * sizeof(nsinteger)); (nsinteger idx = 0; idx < size; ++idx) perm[idx] = idx; nsinteger permutationcount = 0; --size; nsmutablearray *perms = [nsmutablearray array]; { nsmutablearray *newperm = [nsmutablearray array]; (nsinteger = 0; <= size; ++i) [newperm addobject:[self objectatindex:perm[i]]]; [perms addobject:newperm]; } while ((perm = pc_next_permutation(perm, size)) && ++permutationcount < max_permutation_count); free(perm); homecoming perms; } - (nsarray *)allpermutationsarrayofstrings { nsinteger size = [self count]; nsinteger *perm = malloc(size * sizeof(nsinteger)); (nsinteger idx = 0; idx < size; ++idx) perm[idx] = idx; nsinteger permutationcount = 0; --size; nsmutablearray *perms = [nsmutablearray array]; { nsmutablestring *newperm = [[[nsmutablestring alloc]initwithstring:@"" ]autorelease]; (nsinteger = 0; <= size; ++i) { [newperm appendstring:[self objectatindex:perm[i]]]; } [perms addobject:newperm]; } while ((perm = pc_next_permutation(perm, size)) && ++permutationcount < max_permutation_count); free(perm); homecoming perms; } @end

my code thought prepare this:

for ( nsinteger = 1; <= thecount; i++) { nsrange therange2; therange2.location = 0; therange2.length = i; nslog(@"location: %i (len: %i) is: '%@'",therange2.location,therange2.length,[array subarraywithrange:therange2]); nsarray *allwordsforthislength = [[array subarraywithrange:therange2] allpermutationsarrayofstrings]; (nsmutablestring *thestring in allwordsforthislength) { nslog(@"adding %@ possible word",thestring); [allwords addobject:thestring]; }

i know not efficient..but trying test.

this got:

2011-07-07 14:02:19.684 ta[63623:207] total letters in word: 3 2011-07-07 14:02:19.685 ta[63623:207] location: 0 (len: 1) is: '( t )' 2011-07-07 14:02:19.685 ta[63623:207] adding t possible word 2011-07-07 14:02:19.686 ta[63623:207] location: 0 (len: 2) is: '( t, h )' 2011-07-07 14:02:19.686 ta[63623:207] adding th possible word 2011-07-07 14:02:19.687 ta[63623:207] adding ht possible word 2011-07-07 14:02:19.688 ta[63623:207] location: 0 (len: 3) is: '( t, h, e )' 2011-07-07 14:02:19.688 ta[63623:207] adding possible word 2011-07-07 14:02:19.689 ta[63623:207] adding teh possible word 2011-07-07 14:02:19.690 ta[63623:207] adding hte possible word 2011-07-07 14:02:19.691 ta[63623:207] adding het possible word 2011-07-07 14:02:19.691 ta[63623:207] adding eth possible word 2011-07-07 14:02:19.692 ta[63623:207] adding eht possible word

as can see, no 1 or 2 letter words -- pulling hair out! (and don't have much spare!)

an easy thing take subsets of size k , utilize code have generate permutations of subset. easy, not efficient.

here's improve approach. generating permutations lexicographically in first routine:

1234 1243 1324 1342 1423 ...

each time phone call nsinteger *pc_next_permutation(nsinteger *perm, const nsinteger size), next permutation in lex order finding right position change. when that, truncate spot changed following:

1234 123 12 1 1243 124 1324 132 13 1342 134 1423 142 14 1432 143 2143 214 21 2 ...

i hope thought clear. here's 1 way implement (in objective c-like pseudocode).

-(nsmutablearray *)nextperms:(perm *)word { int n = word.length; (int i=n-1; > 0; ++i) { if (word[i-1] < word[i]) { break; } else if (i==1) { = 0; } } // @ point, i-1 leftmost position alter if (i == 0) { homecoming nil; } = i-1; // @ point, leftmost position alter perm *nextword = word; (int j=1; j <= n-i; ++j) { nextword[i+j] = word[n-j]; } nextword[i] = nextword[i+1]; nextword[i+1] = word[i]; // @ point, nextperm next permutation in lexicographic order. nsmutablearray *permlist = [[nsmutablearray alloc] init]; (int j=i; j<n; ++j) { [permlist addobject:[nextword subwordwithrange:nsmakerange(0,i)]]; } homecoming [permlist autorelease]; }

this homecoming array partial permutations described above. input nextperms should lastobject of output of nextperms.

iphone objective-c ios sdk permutation