组合学问题

其中每个数字表示一个对象，值表示颜色。 同样有一种方法可以为四个对象分配四种颜色： 1234 1112 1122 1222 1212 就我的目的而言，具体颜色可以互换（其他 字样， 1112与2221相同。重要的是确定并且 枚举共享或独特颜色的模式。 我会非常感谢能帮助我的人。 > 算法或此问题的C代码。虽然我可以为这个简单的案例手工列举所有 的可能性，但我需要为 开发代码，从1到k颜色分配（和枚举）的一般问题 到k个对象。感谢您的帮助！ Michael ma ***** @ ucsd。 edu 解决方案 2003年10月28日星期二10:12:05 -0800，Carnosaur写道： 大家好， 我正在尝试编写一个程序，它将列举为4个对象分配1到4种颜色的所有可能的组合。例如，有一种方法可以将单个颜色分配给四个对象，这可能会被枚举为： 1111 从阅读开始这个： http：/ /www.eskimo.com/~scs/C-faq/top.html 我会非常感谢能帮助我解决算法或C代码的人对于这个问题。虽然我可以为这个简单的案例手工列举所有可能性，但是我需要开发代码来解决从k到k对象分配（和枚举）1到k种颜色的一般问题。谢谢你的帮助！ 在你向新闻组询问offtopic之前，我会问你的教授帮助 不喜欢为人们做家庭作业。在他让你进入 之后，如果你的C代码有问题，你可以得到正确的方向，然后请求帮助。 Michael ma*****@ucsd.edu BTW，下次你要求某人 做你的功课时，我会留下你的学校电子邮件地址。有些人可能会倾向于联系你的 大学或教授。 问候， 杰克 Carnosaur写道： 大家好， 我正在努力编写一个可以枚举所有可能的程序将1到4种颜色分配给4个对象的组合。例如，有一种方法可以将单个颜色分配给四个对象，这可能会被枚举为： 1111 生成枚举简单。最直接的方法是 有一个整数数组，其中每个索引代表一个对象。然后， 你以类似于里程表的方式增加价值。 [snip]为了我的目的，特定的颜色是可以互换的（在其他 这部分有点困难。我的第一个倾向是在枚举上定义一组 等价类，然后存储每个 唯一等价。这可能很简单。例如，你 表示1112相当于2221.你可以将这些数据分类为 31.另一个例子是1222,3444等等于13然而 另一个例子可能是1223,1331,3112等等等于 121.但是，确切的分类并不清楚你的 描述。 / david - 安德烈，一个简单的农民，只有一个当他悄悄地沿着东墙悄悄地说：安德烈，悄悄......安德烈，蠕动......安德烈，匍匐。' - 未知 David Rubin写道： Carnosaur写道： 大家好， 我正在尝试编写一个程序，它将列举为4个对象分配1到4种颜色的所有可能的组合。例如，有一种方法可以将单个颜色分配给四个对象，可以将其枚举为： 1111 生成枚举简单。最直接的方法是使用一个整数数组，其中每个索引代表一个对象。然后，你以类似于里程表的方式增加值。 [snip] 就我的目的而言，具体的颜色是可以互换的（换句话说，1112与2221相同）。重要的是识别和识别共享或独特颜色的模式。 这部分有点困难。 通过一些数学计算，它变得更容易。 OP的问题开始于 4 x 4 x 4 x 4 可能的颜色组合。如果他列举了这个范围内所有可能的值 ，他会列举所有可能的颜色组合。 如果我试图解决这类问题，而不是单独枚举每个 颜色（即四个嵌套循环），我只是简单地枚举所有 颜色作为范围，并将它们分成单独的值。 br /> 例如（未经测试的代码） { 无符号长调色板; for（palette = 0; palette<（4 * 4 * 4 * 4）; ++ palette） { unsigned long sample = palette; char * color [] = {" red"，" yellow"，" blue"，" green"）; printf（ "％s，"，color [sample％4]）; sample / = 4; printf（"％s，"，color [sample ％4]）; sample / = 4; printf（"％s，"，color [sample％4]）; sample / = 4; printf（"％s \ n"，color [samp le％4]）; } } 然而，他后来的限制表明没有颜色可以重复，并且 这减少了他的可能性 4 x 3 x 2 x 1 组合。这个组合要少得多，虽然这个想法会和以前一样。例如（再次，未经测试的代码） { 无符号长调色板; for（palette = 0 ; palette<（4 * 3 * 2 * 1）; ++ palette） { unsigned long sample = palette; char * color [] = {" red，yellow，blue，green）; printf（"％s，"，color [样本％4]）; 样本/ = 4; printf（"％s，"，color [sample％4]）; sample / = 4; printf（"％s，"，color [sample％4]）; sample / = 4; printf（"％s \ n"，color [sample％4]）; } } - Lew Pitcher，IT顾问，应用程序架构 企业技术解决方案，道明银行金融集团 （此处表达的意见是我自己的意见，而不是我的雇主的意见） Hi all,I am trying to write a program that will enumerate all possiblecombinations of assigning 1 to 4 colors to 4 objects. For example,there is one way to assign a single color to four objects, which mightbe enumerated as:1111where each digit indicates an object and values indicate color.Similarly there is one way to assign four colors to four objects:1234Similarly, here are the ways to assign two colors to four objects:1112112212221212For my purposes, the specific colors are interchangeable (in otherwords, 1112 is the same as 2221). All that matters is identifying andenumerating patterns of shared or unique colors.I would be extremely grateful to anyone that would help me with thealgorithm or C code for this problem. Although I can enumerate allpossibilities by hand for this simple case, I need to develop code forthe general problem of assigning (and enumerating) from 1 to k colorsto k objects. Thanks for any help!Michael ma*****@ucsd.edu 解决方案 On Tue, 28 Oct 2003 10:12:05 -0800, Carnosaur wrote: Hi all, I am trying to write a program that will enumerate all possible combinations of assigning 1 to 4 colors to 4 objects. For example, there is one way to assign a single color to four objects, which might be enumerated as: 1111Start by reading this: http://www.eskimo.com/~scs/C-faq/top.html I would be extremely grateful to anyone that would help me with the algorithm or C code for this problem. Although I can enumerate all possibilities by hand for this simple case, I need to develop code for the general problem of assigning (and enumerating) from 1 to k colors to k objects. Thanks for any help!I would ask your professor for help before you ask offtopic to a newsgroupthat doesn''t like to do homework for people. After he gets you going inthe right direction if you have problems with the C code post what you''vegot and ask for help then. Michael ma*****@ucsd.eduBTW, I''d leave your school email address out next time you ask for someoneto do your homework. Some people may feel inclined to contact youruniversity or professor.Regards,JakeCarnosaur wrote: Hi all, I am trying to write a program that will enumerate all possible combinations of assigning 1 to 4 colors to 4 objects. For example, there is one way to assign a single color to four objects, which might be enumerated as: 1111Generating the enumerations is easy. The most straightforward way is tohave an array of integers where each index represents an object. Then,you increase the values in a similar manner to an odometer.[snip] For my purposes, the specific colors are interchangeable (in other words, 1112 is the same as 2221). All that matters is identifying and enumerating patterns of shared or unique colors.This part is a bit more difficult. My first inclination is to define aset of equivalence classes on the enumerations, and then store the eachunique equivalence. This might be straightforward. For example, Youstated that 1112 is equivalent to 2221. You can classify these datum as31. Another example, is 1222, 3444, etc which are equivalent to 13. Yetanother example might be 1223, 1331, 3112, etc which are equivalent to121. However, the precise classification is not clear from yourdescription./david--Andre, a simple peasant, had only one thing on his mind as he creptalong the East wall: ''Andre, creep... Andre, creep... Andre, creep.''-- unknownDavid Rubin wrote: Carnosaur wrote:Hi all,I am trying to write a program that will enumerate all possiblecombinations of assigning 1 to 4 colors to 4 objects. For example,there is one way to assign a single color to four objects, which mightbe enumerated as:1111 Generating the enumerations is easy. The most straightforward way is to have an array of integers where each index represents an object. Then, you increase the values in a similar manner to an odometer. [snip]For my purposes, the specific colors are interchangeable (in otherwords, 1112 is the same as 2221). All that matters is identifying andenumerating patterns of shared or unique colors. This part is a bit more difficult.With a bit of math, it becomes easier.The OP''s problem starts of with4 x 4 x 4 x 4possible combinations of colours. If he enumerated all the possible valuesin this range, he would enumerate all the possible colour combinations.If I were trying to solve this sort of problem, instead of enumerating eachcolour seperately (i.e. four nested loops), I would simply enumerate all thecolours as a range, and divide them out into seperate values.For instance (untested code){unsigned long palette;for (palette = 0; palette < (4*4*4*4); ++palette){unsigned long sample = palette;char *colour[] = {"red","yellow","blue","green");printf("%s, ",colour[sample%4]);sample /= 4;printf("%s, ",colour[sample%4]);sample /= 4;printf("%s, ",colour[sample%4]);sample /= 4;printf("%s\n",colour[sample%4]);}}However, his later restrictions indicate that no colour may be repeated, andthis reduces his possibilities to4 x 3 x 2 x 1combinations. That''s considerably fewer combinations to go through, althoughthe idea would be the same as before. For example (again, untested code){unsigned long palette;for (palette = 0; palette < (4*3*2*1); ++palette){unsigned long sample = palette;char *colour[] = {"red","yellow","blue","green");printf("%s, ",colour[sample%4]);sample /= 4;printf("%s, ",colour[sample%4]);sample /= 4;printf("%s, ",colour[sample%4]);sample /= 4;printf("%s\n",colour[sample%4]);}}--Lew Pitcher, IT Consultant, Application ArchitectureEnterprise Technology Solutions, TD Bank Financial Group(Opinions expressed here are my own, not my employer''s) 这篇关于组合学问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！