Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

All n-variable combinations can exist within a word

  1. Aug 28, 2004 #1
    All n-variable combinations can exist within a word;
    n=1 | a
    n=2 | ab
    n=3 | cabca

    Is the fourth shortest word cabdcabcdabcadbca, and how long is the n:th word?
     
  2. jcsd
  3. Aug 28, 2004 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What about ba?

    Or bac?
     
  4. Aug 29, 2004 #3
    backwards cab = bac
     
  5. Aug 29, 2004 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    so backwards is permissible, why isn't any other random ordering also equivalent? (ie, exactly what is the full question you want the answer to, seeing as you've given us incomplete information?)
     
  6. Sep 20, 2004 #5
    I ment all permutations, but i hoped i could avoid that word
     
  7. Sep 20, 2004 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    that still doesn't make it a well formed question though.
     
  8. Sep 21, 2004 #7
    Dude, what the hell are you saying?
     
  9. Sep 21, 2004 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    well, if that's aimed at me, cab counts as the same string as bac for this question, now what other strings are identified with bac? sariaht's answer is "all combinations", but that means surely that the answer for a,b,c is abc, ssince that contains all strings of length 3 up to all permutations.
     
  10. Sep 21, 2004 #9
    the question as i see it .... i will try to rephrase it ....
    U have a machine suppose that can read from a strip of letters forward as well as backward but only continuous group of n letters ....
    Given letters a,b,c
    find the smallest strip of letters such that the machine can get any combination of abc from that?

    e.g given by sariaht for 3 letters,
    cabca -- length of 5

    Question now asks to find the smallest strip length for n letters.

    -- AI
     
  11. Sep 28, 2004 #10
    Exactly!

    What is the smallest word with all permutations of n variables?
     
  12. Sep 28, 2004 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    and as we keep pointing out, your examples do not contain all possible permutations

    n=2 ab doesn't contain ba, for instance, however you say this doesn't matter since ba is ab backwards, so what other permutations are equivalent to abc, say? only cba? why not acb? what particularly odd an arbitrary rules do you have that you're not telling us


    edit: just read two posts back, so fowards and backwards are the only permissible variations? fine.
     
    Last edited: Sep 28, 2004
  13. Sep 28, 2004 #12
    Sariaht,
    i haven't given this much thought but i think i get,
    ::n!/2 + n - 1::

    Actually i have assumed something in my logic here , i will put my logic later if i get the time to actually prove my assumption.

    -- AI
     
  14. Sep 28, 2004 #13

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I think Tenali's right.

    That would be my guess too.
     
    Last edited: Sep 28, 2004
  15. Sep 28, 2004 #14
    what!!?

    Have I misunderstod the meaning of permutations?

    Yes I have, sorry!

    What is the smallest word with all n letters long permutations of n variables?
     
  16. Sep 28, 2004 #15
    LOL!
    the proof of the assumption i made was so damn easy ....
    man it skipped my visualisation for such a long time ....
    So if my answer is right, i won't give it away just now ......
    :wink:

    -- AI
     
  17. Sep 29, 2004 #16

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Here's how you start it:

    write out abcd...e whatever the n letters are. then cycle through by putting the abcd.. after it. pick a permutation you've not got, repeat, count and leave this question alone, please.
     
  18. Sep 30, 2004 #17
    Wonder if you can mathematically calibrate the length of the word.
     
  19. Sep 30, 2004 #18

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    what does calibrate mean in this context, and what;s wrong with the metric 'number of letters in the word'?
     
  20. Oct 1, 2004 #19
    The number of letters x you need must be a function of the number of variables n.
    What is that function f(n) = x

    Not that it makes a difference
     
    Last edited: Oct 1, 2004
  21. Oct 5, 2004 #20
    Oh, i see: n!/2 + n - 1

    Then I know, thanx a lot!

    I couldn't see your answer somehow...

    But that cannot be right, n = 4 gives 15, but the word is 17 letters long

    1 1
    2 2
    3 5
    4 17
    5 ?
     
    Last edited: Oct 5, 2004
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: All n-variable combinations can exist within a word
  1. Existence of N (Replies: 1)

Loading...