permutations II

Discussion in 'C Programming' started by Bill Cunningham, Apr 26, 2009.

  1. Well this is as far as I've got with my permutations program if you call
    it that. This is what I want it to look like though. With a prompt. I have
    to be able to read the number of characters and sift them around. Any hints?

    #include <stdio.h>
    #include <limits.h>

    int main(void)
    {
    char input[CHAR_MAX];
    printf("enter word-> ");
    fflush(stdout);
    fgets(input, CHAR_MAX, stdin);
    }

    Bill
    Bill Cunningham, Apr 26, 2009
    #1
    1. Advertising

  2. Bill Cunningham

    osmium Guest

    "Bill Cunningham" wrrote:

    > Well this is as far as I've got with my permutations program if you
    > call it that. This is what I want it to look like though. With a prompt. I
    > have to be able to read the number of characters and sift them around. Any
    > hints?
    >
    > #include <stdio.h>
    > #include <limits.h>


    Don't include things, such as limits.h, that you don't use. It's confusing.

    > int main(void)
    > {
    > char input[CHAR_MAX];
    > printf("enter word-> ");
    > fflush(stdout);
    > fgets(input, CHAR_MAX, stdin);
    > }


    Decide whether you want to do it recursively or not. Then go back to last
    weekend's hints and follow the ones that pertain to that approach. I think
    most seasoned programmers would favor the recursive approach but YMMV. I
    think there might be easier ways to get your arms around recursion. Have
    you written ANY working program that uses recursion? If not, I would look
    for something a bit simpler to do first.
    osmium, Apr 27, 2009
    #2
    1. Advertising

  3. Bill Cunningham

    Eric Sosman Guest

    osmium wrote:
    > "Bill Cunningham" wrrote:
    >
    >> Well this is as far as I've got with my permutations program if you
    >> call it that. This is what I want it to look like though. With a prompt. I
    >> have to be able to read the number of characters and sift them around. Any
    >> hints?
    >>
    >> #include <stdio.h>
    >> #include <limits.h>

    >
    > Don't include things, such as limits.h, that you don't use. It's confusing.


    He's using CHAR_MAX. There's no good reason why he should
    be using it, but using it he is.

    >> int main(void)
    >> {
    >> char input[CHAR_MAX];
    >> printf("enter word-> ");
    >> fflush(stdout);
    >> fgets(input, CHAR_MAX, stdin);
    >> }

    >
    > Decide whether you want to do it recursively or not. Then go back to last
    > weekend's hints and follow the ones that pertain to that approach. I think
    > most seasoned programmers would favor the recursive approach but YMMV. I
    > think there might be easier ways to get your arms around recursion. Have
    > you written ANY working program that uses recursion? If not, I would look
    > for something a bit simpler to do first.


    --
    Eric Sosman
    lid
    Eric Sosman, Apr 27, 2009
    #3
  4. Bill Cunningham

    Guest

    On 26 Apr, 23:48, "Bill Cunningham" <> wrote:

    >     Well this is as far as I've got with my permutations program if you call
    > it that. This is what I want it to look like though. With a prompt. I have
    > to be able to read the number of characters and sift them around. Any hints?


    define "read the number of characters"
    define "sift them around"


    <snip>
    , Apr 27, 2009
    #4
  5. <> wrote in message
    news:...

    define "read the number of characters"
    define "sift them around"


    <snip>

    I think I need a char** definition here. Maybe I could replace CHAR_MAX
    with 40 or something like that. I'll post something soon that I believe
    might get me closer.

    Bill
    Bill Cunningham, Apr 27, 2009
    #5
  6. Bill Cunningham

    CBFalconer Guest

    osmium wrote:
    > "Bill Cunningham" wrrote:
    >

    ....snip ...
    >
    >> #include <stdio.h>
    >> #include <limits.h>

    >
    > Don't include things, such as limits.h, that you don't use. It's
    > confusing.
    >
    >> int main(void) {
    >> char input[CHAR_MAX];
    >> printf("enter word-> ");
    >> fflush(stdout);
    >> fgets(input, CHAR_MAX, stdin);
    >> }


    Without <limits.h>, how do you suggest discovering the value of
    CHAR_MAX? :)

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.
    CBFalconer, Apr 28, 2009
    #6
  7. <> wrote in message
    news:...

    define "read the number of characters"
    define "sift them around"


    <snip>

    Now I need to understand this factorial formula right first. If a word
    is 7 letters long is this how it is to be figured?

    7*6*5*4*3*2*1=possible permutations?

    Bill
    Bill Cunningham, Apr 28, 2009
    #7
  8. Bill Cunningham

    luserXtrog Guest

    On Apr 27, 6:55 pm, "Bill Cunningham" <> wrote:
    > <> wrote in message
    >
    > news:...
    >
    > define "read the number of characters"
    > define "sift them around"
    >
    > <snip>
    >
    >     Now I need to understand this factorial formula right first. If a word
    > is 7 letters long is this how it is to be figured?
    >
    > 7*6*5*4*3*2*1=possible permutations?
    >


    Alright. This would be easier in person with paper, but here goes.
    The usual way to tackle this sort of thing is build up a sense
    of the pattern involved. It's rather like constructing an inductive
    proof; you start with the simplest example; then the next one;
    then notice how the two differ and make a prediction about how
    each case will differ from the previous; then you examine the third
    example and check how it jives with the prediction. If your pattern
    applies no matter how many cases you can produce (in a proof, this
    is the inductive step), you're home free.

    With permutations, you're likely to confuse yourself by not
    sufficiently distinguishing between the set of source elements
    (which here is a string) and the ordered selection that needs
    to be generated (which also happens to be a string). On paper,
    this can be made more clear by writing the source vertically
    and constructing your permutations horizontally.

    Example. Permute the single character 'a'.

    source
    a
    permutations: a

    Example. Permute the two characters 'a' and 'b'.

    source
    a
    b
    permutations: ab ba

    With me so far?
    Now you may not be able to fully enunciate the pattern at this
    point. Keep going and something will have to click eventually.

    Example. Permute the characters in "abc".

    source
    a
    b
    c
    permutations:
    abc acb
    bac bca
    cab cba

    Now a pattern has emerged. The pattern was already present in
    the way I (consciously or otherwise) chose to write these down.
    I started by putting something in the leftmost slot and then
    performing the 2-character permutation on the remaining slots
    with the remaining elements.

    I'd recommend you skip in-place manipulations for now.
    Make a copy to use as the source set and make an empty
    array to be filled in with characters selected from the
    source. When you fill a slot erase the character from
    the source. When the source is empty, your string should
    be filled and you can blank out the string and refill
    the source from the *real* source (which you've wisely
    left unmodified for just this purpose). It'll mean
    3 character arrays instead of just one, but if they're
    named sensibly this should help you keep them straight.

    hth
    --
    lxt
    luserXtrog, Apr 28, 2009
    #8
  9. On Mon, 27 Apr 2009 17:45:34 -0400, "Bill Cunningham"
    <> wrote:

    >
    ><> wrote in message
    >news:...
    >
    >define "read the number of characters"
    >define "sift them around"
    >
    >
    ><snip>
    >
    > I think I need a char** definition here. Maybe I could replace CHAR_MAX
    >with 40 or something like that. I'll post something soon that I believe
    >might get me closer.


    Your just guessing again. If you don't know how you intend to use it,
    you don't need it.

    --
    Remove del for email
    Barry Schwarz, Apr 28, 2009
    #9
  10. On Mon, 27 Apr 2009 19:55:47 -0400, "Bill Cunningham"
    <> wrote:

    >
    ><> wrote in message
    >news:...
    >
    >define "read the number of characters"
    >define "sift them around"
    >
    >
    ><snip>
    >
    > Now I need to understand this factorial formula right first. If a word
    >is 7 letters long is this how it is to be figured?
    >
    >7*6*5*4*3*2*1=possible permutations?


    Only if the letters are distinct. There are two permutations of "ab"
    but only one unique permutation of "aa".

    --
    Remove del for email
    Barry Schwarz, Apr 28, 2009
    #10
  11. "luserXtrog" <> wrote in message
    news:...


    Alright. This would be easier in person with paper, but here goes.
    The usual way to tackle this sort of thing is build up a sense
    of the pattern involved. It's rather like constructing an inductive
    proof; you start with the simplest example; then the next one;
    then notice how the two differ and make a prediction about how
    each case will differ from the previous; then you examine the third
    example and check how it jives with the prediction. If your pattern
    applies no matter how many cases you can produce (in a proof, this
    is the inductive step), you're home free.

    With permutations, you're likely to confuse yourself by not
    sufficiently distinguishing between the set of source elements
    (which here is a string) and the ordered selection that needs
    to be generated (which also happens to be a string). On paper,
    this can be made more clear by writing the source vertically
    and constructing your permutations horizontally.

    Example. Permute the single character 'a'.

    source
    a
    permutations: a

    Example. Permute the two characters 'a' and 'b'.

    source
    a
    b
    permutations: ab ba

    With me so far?
    Now you may not be able to fully enunciate the pattern at this
    point. Keep going and something will have to click eventually.

    Example. Permute the characters in "abc".

    source
    a
    b
    c
    permutations:
    abc acb
    bac bca
    cab cba

    Now a pattern has emerged. The pattern was already present in
    the way I (consciously or otherwise) chose to write these down.
    I started by putting something in the leftmost slot and then
    performing the 2-character permutation on the remaining slots
    with the remaining elements.

    I'd recommend you skip in-place manipulations for now.
    Make a copy to use as the source set and make an empty
    array to be filled in with characters selected from the
    source. When you fill a slot erase the character from
    the source. When the source is empty, your string should
    be filled and you can blank out the string and refill
    the source from the *real* source (which you've wisely
    left unmodified for just this purpose). It'll mean
    3 character arrays instead of just one, but if they're
    named sensibly this should help you keep them straight.

    Is this recursion the recursion dmr did his doctorate on? Or
    mathematicall recursion? Anyway Is recursion what I need? I have found this.
    http://publications.gbdirect.co.uk/c_book/chapter4/recursion_and_argument_passing.html
    Bill Cunningham, Apr 28, 2009
    #11
  12. "luserXtrog" <> wrote in message
    news:...


    Alright. This would be easier in person with paper, but here goes.
    The usual way to tackle this sort of thing is build up a sense
    of the pattern involved. It's rather like constructing an inductive
    proof; you start with the simplest example; then the next one;
    then notice how the two differ and make a prediction about how
    each case will differ from the previous; then you examine the third
    example and check how it jives with the prediction. If your pattern
    applies no matter how many cases you can produce (in a proof, this
    is the inductive step), you're home free.

    With permutations, you're likely to confuse yourself by not
    sufficiently distinguishing between the set of source elements
    (which here is a string) and the ordered selection that needs
    to be generated (which also happens to be a string). On paper,
    this can be made more clear by writing the source vertically
    and constructing your permutations horizontally.

    Example. Permute the single character 'a'.

    source
    a
    permutations: a

    Example. Permute the two characters 'a' and 'b'.

    source
    a
    b
    permutations: ab ba

    With me so far?

    So far


    Now you may not be able to fully enunciate the pattern at this
    point. Keep going and something will have to click eventually.

    Example. Permute the characters in "abc".

    source
    a
    b
    c
    permutations:
    abc acb
    bac bca
    cab cba

    Now a pattern has emerged. The pattern was already present in
    the way I (consciously or otherwise) chose to write these down.
    I started by putting something in the leftmost slot and then
    performing the 2-character permutation on the remaining slots
    with the remaining elements.

    Oh ok I see.


    I'd recommend you skip in-place manipulations for now.
    Make a copy to use as the source set and make an empty
    array to be filled in with characters selected from the
    source. When you fill a slot erase the character from
    the source. When the source is empty, your string should
    be filled and you can blank out the string and refill
    the source from the *real* source (which you've wisely
    left unmodified for just this purpose). It'll mean
    3 character arrays instead of just one, but if they're
    named sensibly this should help you keep them straight.

    hth
    --
    lxt
    Bill Cunningham, Apr 28, 2009
    #12
  13. "Bill Cunningham" <> writes:

    > "luserXtrog" <> wrote in message
    > news:...
    >
    > Alright. This would be easier in person with paper, but here goes.

    <snip>
    > Is this recursion the recursion dmr did his doctorate on? Or
    > mathematicall recursion? Anyway Is recursion what I need? I have found this.
    > http://publications.gbdirect.co.uk/c_book/chapter4/recursion_and_argument_passing.html


    Yes. You can do it non-recursive in stead if you want: Keep a
    counter that acts like an odometer but with each digit having its own
    range. For n=4

    0 0 0 0
    1 0 0 0
    2 0 0 0
    3 0 0 0
    0 1 0 0
    1 1 0 0
    2 1 0 0
    3 1 0 0
    0 2 0 0
    1 2 0 0
    2 2 0 0
    3 2 0 0
    0 0 1 0
    1 0 1 0
    2 0 1 0
    3 0 1 0
    0 1 1 0
    1 1 1 0
    2 1 1 0
    3 1 1 0
    0 2 1 0
    1 2 1 0
    2 2 1 0
    3 2 1 0

    We can't count any more because the last counter has only on valid
    value. Can you see the pattern? Could you take an array of n ints an
    make the "next" counter value from it?

    int increment_factorial_counter(int n, int *counter);

    Every time this counter in increased, you can generate the
    permutation it represents (but that bit can wait).

    --
    Ben.
    Ben Bacarisse, Apr 28, 2009
    #13
  14. "Bill Cunningham" <> writes:
    > <> wrote in message
    > news:...

    [...]
    > Now I need to understand this factorial formula right first. If a word
    > is 7 letters long is this how it is to be figured?
    >
    > 7*6*5*4*3*2*1=possible permutations?


    Yes, assuming all the letters are distinct.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Apr 28, 2009
    #14
  15. Bill Cunningham

    luserXtrog Guest

    On Apr 27, 8:39 pm, "Bill Cunningham" <> wrote:
    > "luserXtrog" <> wrote in message
    >
    > news:...
    >

    <snip intro to inductive exploration>

    > I'd recommend you skip in-place manipulations for now.
    > Make a copy to use as the source set and make an empty
    > array to be filled in with characters selected from the
    > source. When you fill a slot erase the character from
    > the source. When the source is empty, your string should
    > be filled and you can blank out the string and refill
    > the source from the *real* source (which you've wisely
    > left unmodified for just this purpose). It'll mean
    > 3 character arrays instead of just one, but if they're
    > named sensibly this should help you keep them straight.
    >
    >     Is this recursion the recursion dmr did his doctorate on? Or
    > mathematicall recursion? Anyway Is recursion what I need? I have found this.http://publications.gbdirect.co.uk/c_book/chapter4/recursion_and_argu...


    I haven't read the paper; if Ben says so (and he does), I have
    no reason to doubt it.

    This link looks like good stuff but not necessarily the most
    pertinent to this problem. The ability to think about the problem
    in terms of recursion is definitely valuable. While the relation
    between factorials and permutation is not necessarily useful
    for producing the permutations (except perhaps for verifying
    that you found the correct number of them!), the recursive
    implementation of the factorial function is definitely useful
    in its own right and could definitely shed some light on
    how to go about constructing a recursive permutation function.
    [goddam! that's a dense sentence!]

    Basically, a recursive function needs to reduce the problem
    to a self-call over a smaller problem.

    I wouldn't say that permutations require recursion, but
    permutations are possibly the perfect means to learn about
    recursion.

    --
    lxt
    luserXtrog, Apr 28, 2009
    #15
  16. Bill Cunningham

    BartC Guest

    "Barry Schwarz" <> wrote in message
    news:...
    > On Mon, 27 Apr 2009 19:55:47 -0400, "Bill Cunningham"
    > <> wrote:
    >
    >>
    >><> wrote in message
    >>news:...
    >>
    >>define "read the number of characters"
    >>define "sift them around"
    >>
    >>
    >><snip>
    >>
    >> Now I need to understand this factorial formula right first. If a word
    >>is 7 letters long is this how it is to be figured?
    >>
    >>7*6*5*4*3*2*1=possible permutations?

    >
    > Only if the letters are distinct. There are two permutations of "ab"
    > but only one unique permutation of "aa".


    How many of "Aa"?

    --
    Bartc
    BartC, Apr 28, 2009
    #16
  17. "BartC" <> writes:
    > "Barry Schwarz" <> wrote in message
    > news:...
    >> On Mon, 27 Apr 2009 19:55:47 -0400, "Bill Cunningham"
    >> <> wrote:

    [...]
    >>>7*6*5*4*3*2*1=possible permutations?

    >>
    >> Only if the letters are distinct. There are two permutations of "ab"
    >> but only one unique permutation of "aa".

    >
    > How many of "Aa"?


    Two, "Aa" and "aA". Why do you ask? (There's been no suggestion that
    uppercase and lowercase letters should be considered equivalent; is
    there some reason they should be?)

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Apr 28, 2009
    #17
  18. "Ben Bacarisse" <> wrote in message
    news:...

    > Yes. You can do it non-recursive in stead if you want: Keep a
    > counter that acts like an odometer but with each digit having its own
    > range. For n=4
    >
    > 0 0 0 0
    > 1 0 0 0
    > 2 0 0 0
    > 3 0 0 0
    > 0 1 0 0
    > 1 1 0 0
    > 2 1 0 0
    > 3 1 0 0
    > 0 2 0 0
    > 1 2 0 0
    > 2 2 0 0
    > 3 2 0 0
    > 0 0 1 0
    > 1 0 1 0
    > 2 0 1 0
    > 3 0 1 0
    > 0 1 1 0
    > 1 1 1 0
    > 2 1 1 0
    > 3 1 1 0
    > 0 2 1 0
    > 1 2 1 0
    > 2 2 1 0
    > 3 2 1 0
    >
    > We can't count any more because the last counter has only on valid
    > value. Can you see the pattern? Could you take an array of n ints an
    > make the "next" counter value from it?


    I don't think so. I don't know how to code it. I'm thinking using for?

    > int increment_factorial_counter(int n, int *counter);
    >
    > Every time this counter in increased, you can generate the
    > permutation it represents (but that bit can wait).
    >
    > --
    > Ben.
    Bill Cunningham, Apr 28, 2009
    #18
  19. Bill Cunningham

    Carl Guest

    Bill Cunningham wrote:
    > "Ben Bacarisse" <> wrote in message
    > news:...
    >
    >> Yes. You can do it non-recursive in stead if you want: Keep a
    >> counter that acts like an odometer but with each digit having its own
    >> range. For n=4
    >>
    >> 0 0 0 0
    >> 1 0 0 0
    >> 2 0 0 0
    >> 3 0 0 0
    >> 0 1 0 0
    >> 1 1 0 0
    >> 2 1 0 0
    >> 3 1 0 0
    >> 0 2 0 0
    >> 1 2 0 0
    >> 2 2 0 0
    >> 3 2 0 0
    >> 0 0 1 0
    >> 1 0 1 0
    >> 2 0 1 0
    >> 3 0 1 0
    >> 0 1 1 0
    >> 1 1 1 0
    >> 2 1 1 0
    >> 3 1 1 0
    >> 0 2 1 0
    >> 1 2 1 0
    >> 2 2 1 0
    >> 3 2 1 0
    >>
    >> We can't count any more because the last counter has only on valid
    >> value. Can you see the pattern? Could you take an array of n ints an
    >> make the "next" counter value from it?

    >
    > I don't think so. I don't know how to code it. I'm thinking using for?
    >
    >> int increment_factorial_counter(int n, int *counter);
    >>
    >> Every time this counter in increased, you can generate the
    >> permutation it represents (but that bit can wait).
    >>
    >> --
    >> Ben.

    >
    >



    I believe you can code it that way. If you are interested, I can post
    the source.
    Carl, Apr 28, 2009
    #19
  20. Bill Cunningham

    BartC Guest

    "Keith Thompson" <> wrote in message
    news:...
    > "BartC" <> writes:
    >> "Barry Schwarz" <> wrote in message
    >> news:...
    >>> On Mon, 27 Apr 2009 19:55:47 -0400, "Bill Cunningham"
    >>> <> wrote:

    > [...]
    >>>>7*6*5*4*3*2*1=possible permutations?
    >>>
    >>> Only if the letters are distinct. There are two permutations of "ab"
    >>> but only one unique permutation of "aa".

    >>
    >> How many of "Aa"?

    >
    > Two, "Aa" and "aA". Why do you ask? (There's been no suggestion that
    > uppercase and lowercase letters should be considered equivalent; is
    > there some reason they should be?)


    In the real world letter case usually has no significance.

    It only seems to be important in C code (and languages created by people
    exposed to C) and Unix file names (possibly for the same reasons).

    --
    Bartc
    BartC, Apr 28, 2009
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Karsten Wutzke

    Permutations of instances in array

    Karsten Wutzke, Mar 2, 2004, in forum: Java
    Replies:
    5
    Views:
    17,709
    Chris Lamprecht
    Mar 4, 2004
  2. Hendrik Maryns
    Replies:
    0
    Views:
    336
    Hendrik Maryns
    Mar 3, 2006
  3. Roger
    Replies:
    1
    Views:
    413
    Martin Magnusson
    Sep 24, 2003
  4. Ed Neukirch

    Permutations

    Ed Neukirch, Dec 24, 2003, in forum: C++
    Replies:
    7
    Views:
    605
    Mike Hewson
    Dec 27, 2003
  5. Daniel Fortin
    Replies:
    3
    Views:
    360
    Frank Schmitt
    Feb 18, 2004
Loading...

Share This Page