Search Results

Search found 148 results on 6 pages for 'permutation'.

facebook twitter digg google delicious technorati stumbleupon myspace wordpress linkedin gmail igoogle windows live tumblr viadeo yahoo buzz yahoo mail yahoo bookmarks favorites email print

Page 1/6 | 1 2 3 4 5 6  | Next Page >

  • Fast permutation -> number -> permutation mapping algorithms

    - by ijw
    I have n elements. For the sake of an example, let's say, 7 elements, 1234567. I know there are 7! = 5040 permutations possible of these 7 elements. I want a fast algorithm comprising two functions: f(number) maps a number between 0 and 5039 to a unique permutation, and f'(permutation) maps the permutation back to the number that it was generated from. I don't care about the correspondence between number and permutation, providing each permutation has its own unique number. So, for instance, I might have functions where f(0) = '1234567' f'('1234567') = 0 The fastest algorithm that comes to mind is to enumerate all permutations and create a lookup table in both directions, so that, once the tables are created, f(0) would be O(1) and f('1234567') would be a lookup on a string. However, this is memory hungry, particularly when n becomes large. Can anyone propose another algorithm that would work quickly and without the memory disadvantage?

    Read the article

  • Generating permutation in Python with specific rule

    - by twfx
    Let say a=[A, B, C, D], each element has a weight w, and is set to 1 if selected, 0 if otherwise. I'd like to generate permutation in the below order 1,1,1,1 1,1,1,0 1,1,0,1 1,1,0,0 1,0,1,1 1,0,1,0 1,0,0,1 1,0,0,0 Let's w=[1,2,3,4] for item A,B,C,D ... and max_weight = 4. For each permutation, if the accum weight has exceeded max_weight, stop calculation for that permutation, move to next permutation. For eg. 1,1,1 --> 6 > 4, exceeded, stop, move to next 1,1,1 --> 6 > 4, exceeded, stop, move to next 1,1,0,1 --> 7 > 4 finished, move to next 1,1,0,0 --> 3 finished, move to next 1,0,1,1 --> 8 > 4, finished, stop, move to next 1,0,1,0 --> 4 finished, move to next 1,0,0,1 --> 5 > 4 finished, move to next 1,0,0,0 --> 1 finished, move to next [1,0,1,0] is the best combination which does not exceeded max_weight 4 My questions are What's the algorithm which generate the required permutation? Or any suggestion I could generate the permutation? As the number of element can be up to 10000, and the calculation stop if the accum weight for the branch exceeds max_weight, it is not necessary to generate all permutation first before the calculation. How can the algo in (1) generate permutation on the fly?

    Read the article

  • Doing permutation of different arrays in perl

    - by nubie2
    Hello! I want to do permutation in perl. For example I have three arrays. ["big", "tiny", "small"] and then I have ["red", "yellow", "green"] and also ["apple", "pear", "banana"]. How do I get: ["big", "red", "apple"] ["big", "red", "pear"] ..etc.. ["small", "green", "banana"] I understand this is called permutation. But I am not sure how to do it. Also I don't know how many arrays I can have. There may be three or four, so I don't want to do nested loop.

    Read the article

  • Graph and permutation problem

    - by user319771
    I have a graph (with nodes and edges) containing symmetry and a group of permutations to label the nodes so no edges are changed (automorphisms). Now I would like to determine for which nodes a permutation exchanges two equivalent (i.e. nodes with the same color or symmetry class) neighboring nodes. When the nodes with equivalent neighbors stay the same, simply checking if the neighbors are exchanged in the permutation is enough. However, when the nodes with equivalent neighbors are also permuted (i.e. there are multiple nodes with the same color/symmetry class with the same equivalent neighbors), the problem becomes more complex. Is there any known algorithm for such a problem? Some remarks: The graph has no coordinates, it's a topology only

    Read the article

  • permutation need help to code

    - by Hunt
    Thank for your reply, first thing i wish to thank you for trying to help me out, and i have post this in few website also no one trying to help at all. For my code, what i wish to do is permutation count. it will count from top to bottom 1,2,3 1,2,3 1,2,3 output to 111 = 1 112 = 1 113 = 1 121 = 1 122 = 1 123 = 1 133 = 1 211 = 1 212 = 1 213 = 1 333 = 1 and continue till all number is count and also store to the array which can check how many count after all code will check the input number and count how many outcome and show the results with how many outcome and each have how many after permutation count. Its hard to do?. Anyway thank you for help.

    Read the article

  • Unsort: remembering a permutation and undoing it.

    - by dreeves
    Suppose I have a function f that takes a vector v and returns a new vector with the elements transformed in some way. It does that by calling function g that assumes the vector is sorted. So I want f to be defined like so: f[v_] := Module[{s, r}, s = Sort[v]; (* remember the permutation applied in order to sort v *) r = g[s]; Unsort[r] (* apply the inverse of that permutation *) ] What's the best way to do the "Unsort"? Or could we get really fancy and have this somehow work: answer = Unsort[g[Sort[v]]]; ADDED: Let's make this concrete with a toy example. Suppose we want a function f that takes a vector and transforms it by adding to each element the next smallest element, if any. That's easy to write if we assume the vector is sorted, so let's write a helper function g that makes that assumption: g[v_] := v + Prepend[Most@v, 0] Now for the function we really want, f, that works whether or not v is sorted: f[v_] := (* remember the order; sort it; call g on it; put it back in the original order; return it *)

    Read the article

  • c permutation of a number

    - by Pkp
    I am writing a program for magic box. As the only way around it is brute force, I wrote a program to compute permutations of a given array using bells algorithm. I wrote in the lines similar to http://programminggeeks.com/c-code-for-permutation/. It does work for array of 3 and 4. It does not work for an arryay of 8 numbers (1,2,3,4,5,6,7,8). I see that the combination 1 2 3 4 5 6 7 8 gets repeated couple of times. Also there are other combinations that gets repeated. I see that certain combinations don't get displayed even. So could someone tell me what is wrong in the program below. Code: include<stdio.h> int len,numperm=1,count=0; display(int a[]){ int i; for(i=0;i<len;i++) printf("%d ",a[i]); printf("\n"); count++; } swap(int *a,int *b){ int temp; temp=*a; *a=*b; *b=temp; } no_of_perm(){ int x; for(x=1;x<=len;x++) numperm=numperm*x; } perm(int a[]){ int x,y; while(count < numperm){ for(x=0;x<len-1;x++){ swap(&a[x],&a[x+1]); display(a); } swap(&a[0],&a[1]); display(a); for(y=len-1;y>0;y--){ swap(&a[y],&a[y-1]); display(a); } swap(&a[len-1],&a[len-2]); display(a); } } main(int argc, char *argv[]){ if(argc<2){ printf("Error\n"); exit(0); } int i,*a=malloc(sizeof(int)*atoi(argv[1])); len=atoi(argv[1]); for(i=0;i<len;i++) a[i]=i+1; no_of_perm(); perm(a); }

    Read the article

  • Create many constrained, random permutation of a list

    - by Eyal
    I need to make a random list of permutations. The elements can be anything but assume that they are the integers 0 through x-1. I want to make y lists, each containing z elements. The rules are that no list may contain the same element twice and that over all the lists, the number of times each elements is used is the same (or as close as possible). For instance, if my elements are 0,1,2,3, y is 6, and z is 2, then one possible solution is: 0,3 1,2 3,0 2,1 0,1 2,3 Each row has only unique elements and no element has been used more than 3 times. If y were 7, then 2 elements would be used 4 times, the rest 3.

    Read the article

  • Permutation algorithm without recursion? Java

    - by Andreas Hornig
    Hi, I would like to get all combination of a number without any repetation. Like 0.1.2, 0.2.1, 1.2.0, 1.0.2, 2.0.1, 2.1.0. I tried to find an easy scheme but couldn't find so I drawed a graph/tree for it and this screams to use recursion. But I would like to do it without, if this is possible. So could anyone please help me how to do that? Thank you in advance, Andreas

    Read the article

  • create program in c for permutation combination and showing frequency

    - by Vishal Oswal
    I have 2 strings where I have saved fixed 20 characters and these are “A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T” and same 20 char in string 2. so I will get 400 combinations of 2 character sets like AA,AB,AC,AD,AE,AF,……………AT BA,BB,BC,BD,BE,BF,…………..BT CA,CB,CC,CD,CE,CF……………CT This way we will get 400 combinations (Which program I have created successfully) but then user will put the value till 31 characters witch will be treated as 3rd string for E.g. “ABCDDAAAB” now I have to check the frequency of user input in the sequence of 12,23,34,45,56,67,78,89 (2 CHAR SET) means AB,BC,CD,DD,DA,AA,AA,AB and need to show the frequency of user input OUTPUT: AB=2 BC=1 CD=1 DD=1 DA=1 AA=2 please its urgent

    Read the article

  • Permutation of Strings in C++

    - by cam
    I'm looking for just a simple method for permutating strings/integers in C++. I can easily do it in C#, but I'm just learning C++ and can't seem to find the right methods. Can someone show me a simple example that will find all permutations of an integer? And then the exact same for a string?

    Read the article

  • How can I use the Fisher-Yates shuffle while ensuring my permutation is even?

    - by Mithrax
    I'm interested making an implementation of the 14-15 puzzle: I'm creating an array with the values 0 - 15 in increasing order: S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 } Now, what I want to do is shuffle them to create a new instance of the puzzle. However, I know that if I create a board with an "odd permutation" than it is unsolvable. Wikipedia says I need to create the puzzle with an even permutation. I believe this means that I simply have to do ensure I do an even number of swaps? How would I modify Fisher-Yates so I ensure I end up with an even permutation at the end? If I do a swap for every element in the array that would be 16 swaps which I believe would be an even permutation. However, do I need to be concerned about swapping with itself? Is there any other way to ensure I have a valid puzzle?

    Read the article

  • How can I ensure that when I shuffle my puzzle I still end up with an even permutation?

    - by Mithrax
    I'm interested making an implementation of the 14-15 puzzle: I'm creating an array with the values 0 - 15 in increasing order: S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 } Now, what I want to do is shuffle them to create a new instance of the puzzle. However, I know that if I create a board with an "odd permutation" than it is unsolvable. Wikipedia says I need to create the puzzle with an even permutation. I believe this means that I simply have to do ensure I do an even number of swaps? How would I modify Fisher-Yates so I ensure I end up with an even permutation at the end? If I do a swap for every element in the array that would be 16 swaps which I believe would be an even permutation. However, do I need to be concerned about swapping with itself? Is there any other way to ensure I have a valid puzzle?

    Read the article

  • Using a permutation table for simplex noise without storing it

    - by J. C. Leitão
    Generating Simplex noise requires a permutation table for randomisation (e.g. see this question or this example). In some applications, we need to persist the state of the permutation table. This can be done by creating the table, e.g. using def permutation_table(seed): table_size = 2**10 # arbitrary for this question l = range(1, table_size + 1) random.seed(seed) # ensures the same shuffle for a given seed random.shuffle(l) return l + l # see shared link why l + l; is a detail and storing it. Can we avoid storing the full table by generating the required elements every time they are required? Specifically, currently I store the table and call it using table[i] (table is a list). Can I avoid storing it by having a function that computes the element i, e.g. get_table_element(seed, i). I'm aware that cryptography already solved this problem using block cyphers, however, I found it too complex to go deep and implement a block cypher. Does anyone knows a simple implementation of a block cypher to this problem?

    Read the article

  • Prolog: permutations check and multiple answers

    - by Adrian
    Continuing to learn prolog, I'm trying to write a permutation(L1, L2) predicate. It should return true, only if L1 can be made up of all elements in L2. My code so far is the following: permutation([], []). permutation([H|T], L2) :- remove(L2, H, R), permutation(T, R). Assuming that the predicate remove(L1, X, R) functions correctly, and it removes X from L1, I do not get correct results: ?- permutation([1],[1]). true ; false. ?- permutation([1, 2],[1]). true ; false. ?- permutation([1, 2],[1, 2]). true ; false. ?- permutation([1],[1, 2]). false. What am I missing. Subquestion: What happens when the remove predicate returns two answers? My implementation returns the new, correct list, and then after pressing ; it returns the original list. Which answer does permutation predicate use? ?- remove([1,2,3], 3, R). R = [1, 2] ; R = [1, 2, 3].

    Read the article

  • doing a full permutation search and replace on a string

    - by user73307
    I'm writing an app that does something like a custom number (licence) place generator tool where if I ask for the plate "robin" it will suggest I try: r0bin rob1n r0b1n Are there any published algorithms which can do this? It has to be able to handle replacing single letters with multiples, e.g. m with rn and vise-versa and not fall over if it replaces an i with an l then comes to check the l and replaces it back to an i. The list of what gets swapped with what is going to be user input but I'm not expecting a huge list, possibly 10 pairs at most. I'll be implementing this in Ruby or Python but I should be able to convert code from any other language.

    Read the article

  • 2d array permutation proof [migrated]

    - by FGM
    I want to know if it's possible to get any possible combination of a 4x4 integer array given three rules: you may shift any column up or down you may shift any row left or right you may shift the entire array left, right, up, or down That is, you can transform: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] into any possible combination of a 4x4 array of the same 16 values, given those three rules. Basically, I just want to know if there are impossible combinations.

    Read the article

  • Another Permutation Word Conundrum... With Linq?

    - by CraigF
    I have seen many examples of getting all permutations of a given set of letters. Recursion seems to work well to get all possible combinations of a set of letters (though it doesn't seem to take into account if 2 of the letters are the same). What I would like to figure out is, could you use linq (or not) to get all possible combinations of letters down to 3 letter combinations. For example, given the letters: P I G G Y I want an array of all possible cominations of these letters so I can check against a word list (scrabble?) and eventually get a list of all possible words that you can make using those letters (from 3 letters up to the total, in this case 5 letters).

    Read the article

  • question about permutation problem

    - by davit-datuashvili
    i have posted similar problem here http://stackoverflow.com/questions/2920315/permutation-of-array but i want following we know that with length n there is n! possible permutation from which one such that all element are in order they are in sorted variant so i want break permutation when array is in order and print result but something is wrong i think that problem is repeated of permutation here is my code import java.util.*; public class permut{ public static Random r=new Random(); public static void display(int a[],int n){ for (int i=0;i<n;i++){ System.out.println(a[i]); } } public static void Permut(int a[],int n){ int j=0; int k=0; while (j<fact(n)){ int s=r.nextInt(n); for (int i=0;i<n;i++){ k=a[i]; a[i]=a[s]; a[s]=k; } j++; if (sorted(a,n)) display(a,n); break; } } public static void main(String[]args){ int a[]=new int[]{3,4,1,2}; int n=a.length; Permut(a,n); } public static int fact(int n){ if (n==0 || (n==1) ) return 1; return n*fact(n-1); } public static boolean sorted(int a[],int n ){ boolean flag=false; for (int i=0;i<n-1;i++){ if (a[i]<a[i+1]){ flag=true; } else{ flag=false; } } return flag; } } can anybody help me? result is nothing

    Read the article

  • Correct permutation cycle for Verhoeff algorithm

    - by James
    Hello, I'm implementing the Verhoeff algorithm for a check digit scheme, but there seems to be some disagreement in web sources as to which permutation cycle should form the basis of the permutation table. Wikipedia uses: (36)(01589427) while apparently, Numerical Recipies uses a different cycle and this book uses: (0)(14)(23)(56789), quoted from a 1990 article by Winters. It also notes that Verhoeff used the one Wikipedia quotes. Now, my number theory is a little rusty, but the Wikipedia cycle clearly will repeat after the 8th power, while the book one will take 10, despite it saying that s^8=s. Table 2.14(b) has other errors in the 2-cycles, so this is dubious anyway. Unfortunately, I don't have copies of the original articles (and am too tight to pay/disgusted that 40-year old knowledge is still being held to ransom by publishers), nor a copy of Numerical Recipes to check (and am loath to install their paranoia-induced copy protection plug-in to view online). So does any one know which is correct? Are they both correct?

    Read the article

  • Reversing permutation of an array in Java efficiently

    - by HansDampf
    Okay, here is my problem: Im implementing an algorithm in Java and part of it will be following: The Question is to how to do what I will explain now in an efficient way. given: array a of length n integer array perm, which is a permutation of [1..n] now I want to shuffle the array a, using the order determined by array perm, i.e. a=[a,b,c,d], perm=[2,3,4,1] ------ shuffledA[b,c,d,a], I figured out I can do that by iterating over the array with: shuffledA[i]=a[perm[i-1]], (-1 because the permutation indexes in perm start with 1 not 0) Now I want to do some operations on shuffledA... And now I want to do the reverse the shuffle operation. This is where I am not sure how to do it. Note that a can hold an item more than once, i.e. a=[a,a,a,a] If that was not the case, I could iterate perm, and find the corresponding indexes to the values. Now I thought that using a Hashmap instead of the the perm array will help. But I am not sure if this is the best way to do.

    Read the article

  • How do I tell GWT to not compile a permutation for gears

    - by Clinton Bosch
    I have included gwt-html5-geolocation into my GWT project and was disappointed to find that it doubled up on my number of permutations compiled. Apparently if the browser does not support geolocation API then it falls back to use gears to find out your location. Is there a way to NOT compile a permutation for gears similar to the way you can tell GWT to only compile certain browser permutations? (the geolocation stuff is very much a nice-to-have and frankly if the client is running an old browser then I am happy not to get their location) Thanks

    Read the article

facebook twitter digg google delicious technorati stumbleupon myspace wordpress linkedin gmail igoogle windows live tumblr viadeo yahoo buzz yahoo mail yahoo bookmarks favorites email print

1 2 3 4 5 6  | Next Page >