2
\$\begingroup\$

I have a very long sequence of letters (>20000 elements long). I want to permute them so that I have another sequence using the same letters but in a different order but still with the property of no repeats. e.g. ABABABA does not have repeats, but ABCDEEABCDE does as E is repeating itself in the middle.

I cannot accomplish this just yet for a sequence of >10000 or so. I can do it for smaller sequences (e.g. 1000) but it's still really slow.

Sample data (the original population of letter codes):

x = read.table("https://gist.githubusercontent.com/jalapic/9f65738271dc86a5541f4d3ff843cb6a/raw/2098f6aeb3c016653552b11056ee22ef52ef6acb/seq",
               header=F, sep="", na.strings="NA",  strip.white=TRUE)

x <- as.character(x[[1]])
x <- gsub("Z", "", x) #remove Zs - they are spaces that should be removed
x

I have modified some suggested solutions to this. It's all in R, but I have to think that a C++ solution may work better.

Here, I generate a subsample of 1000 elements drawn from the original population with probability of being drawn being the relative frequency of each letter in the original population:

uncollapsex <- function (x, n = 1) {substring(x, seq(1, nchar(x), n), seq(n, 

probs = table(uncollapsex(x))

This is a series of loops that will do the following:

  1. Generate a sample of 1000 elements drawn from the original population.

  2. Attempt 5 times to find a way of putting the elements together but not allowing for repeats.

  3. If a solution cannot be found, redo the sample and start again.

  4. Repeat this process 10 times to try and get 10 solutions for 10 different samples of 1000 elements.

      Nres = 10

      res_list <- vector("list", Nres)  #results

    for (q in 1:Nres) {

    seq1 = sample(names(probs),prob=probs,1000,T) 

    res_vec=NA

    counter=0

    while(is.na(res_vec[length(res_vec)]) | counter<=5) {

      counter = counter+1

      popul=seq1

      res_vec=rep(NA_character_,length(seq1))
new_draw=sample(popul,1)


      popul=popul[-match(new_draw,popul)]

      res_vec[1]=new_draw

      for (j in 2:length(seq1)) {

        while((new_draw==res_vec[j-1])&any(res_vec[j-1]!=popul)) {

            new_draw=sample(popul,1)

        }

        if (new_draw==res_vec[j-1]) {

          break

        }

        res_vec[j]=new_draw

        popul=popul[-match(new_draw,popul)]

      }

    }  

    res_list[[q]] <- res_vec

    }

I'm really hoping that someone can identify a faster more efficient way of generating permuted sequences of non-repeating elements. Either of length 1000 with the elements drawn from the original population, or to be able to actually permute the original population itself.

The aim is to generate 10,000 permuted samples (of either 1000 length or the original length) as part of a Monte Carlo simulation.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.