Talk:Find the missing permutation: Difference between revisions
→Simple solution: (yes)
(→Simple solution: (yes)) |
|||
| (5 intermediate revisions by 4 users not shown) | |||
Line 80:
: I would prefer the universe of symbols to be undefined, and for the code to be generic. You might as well think of the data being 0x41, 0x42, 0x43 and 0x44 integer values, 65.0f, 66.0f, 67.0f, 68.0f, or even Rosemary, Paprika, Sage, Thyme; My intent was to consider and compare the permutations of symbols, not <em>necessarily</em> the exact symbols used. It would probably be best to avoid hardcoded assumptions about the universe of symbols --[[User:Short Circuit|Michael Mol]] 05:14, 28 December 2009 (UTC)
: You could also exhibit both solutions, stating in the adjoining text that one is more general than the other. Like that you'd illustrate a point about the J language as well as providing the solution in various levels of elegance. –[[User:Dkf|Donal Fellows]] 13:46, 28 December 2009 (UTC)
== Fortran example incorrect? ==
The fortran example was marked incorrect. Indeed, the result is wrong when compiled with gfortran. However, g95 gives the correct result. I believe this to be a bug in gfortran. I narrowed down the problem in the following test program:
<lang fortran>program missing_permutation_test
implicit none
character (4), dimension (23), parameter :: list = &
& (/'ABCD', 'CABD', 'ACDB', 'DACB', 'BCDA', 'ACBD', 'ADCB', 'CDAB', &
& 'DABC', 'BCAD', 'CADB', 'CDBA', 'CBAD', 'ABDC', 'ADBC', 'BDCA', &
& 'DCBA', 'BACD', 'BADC', 'BDAC', 'CBDA', 'DBCA', 'DCAB'/)
integer :: i
write (*, *) list (:) (1 : 1)
write (*, *) list (1) (1 : 1)
write (*, *) list (:) (1 : 1) == list (1) (1 : 1)
i = 1
write (*, *) list (1) (i : i)
write (*, *) list (:) (1 : 1) == list (1) (i : i)
end program missing_permutation_test</lang>
The output of this program when compiled with gfortran is:
<lang> ACADBAACDBCCCAABDBBBCDD
A
T F T F F T T F F F F F F T T F F F F F F F F
A
F F F F F F F F F F F F F F F F F F F F F F F</lang>
It seems to me that comparing <code>list (:) (1 : 1)</code> to either <code>list (1) (1 : 1)</code> or <code>list (1) (i : i)</code> when <code>i = 1</code> should give the same result. However, I am not 100% certain about my claim.
When compiled with g95 we get:
<lang> ACADBAACDBCCCAABDBBBCDD
A
T F T F F T T F F F F F F T T F F F F F F F F
A
T F T F F T T F F F F F F T T F F F F F F F F</lang>
For now, I will leave the "incorrect" label, until we find a definite answer.
: I investigated this issue a bit further. The posted program is a correct fortran program (90 and later) and should give the correct result (see e.g. [http://groups.google.com/group/comp.lang.fortran/browse_thread/thread/b327e38e69e4e622/2ea18cbd2a5af40f?lnk=raot this thread]). The version of gfortran tried by me (4.3.3 20080904 (prerelease)) gives a wrong result. More recent versions give the correct result. I am removing the "incorrect label". --[[User:Dsnouck|Dsnouck]] 07:56, 27 May 2010 (UTC)
:: The bug is more subtle than it seemed; the problem is bound to how gfortran handles parameters, in fact removing the parameter attribute it works the same in gfortran. I suppose there's also some relationship with how "strings" are handled. Using 1:1 and i:i "indipendently" does not change the result, as we expect, but when combined with == and slicing of a var with parameter attribute (immutable), the problem arises (and also it seems the error propagate, see the following long test code)
<lang fortran>program test
implicit none
character (2), dimension (2), parameter :: list = (/'ab', 'ba'/)
character (2), dimension (2) :: la = (/ 'a', 'b' /)
character, dimension(2) :: p
character :: t, t1
character(2) :: tt
integer :: i
i = 1
write (*, *) 'list(:)(1:1) = ', list (:) (1:1) ! a, b
write (*, *) ' size of prev = ', size(list (:) (1:1)) ! check that it is a, b
write(*, *) 'shape of prev : ', shape(list (:) (1:1))
write (*, *) '1:1 = ', list (1) (1:1) ! a
write (*, *) 'i:i = ', list (1) (i:i) ! a both! no bug is shown here by gfortran
t = list(1)(i:i) ! t = 'a'
t1 = list(1)(1:1) ! t1 = 'a' (character(1))
tt = list(1)(i:i) ! tt = 'a' (character(2))
write(*, *) 't use i:i = ', t, '| len = ', len(t)
write(*, *) 't1 use 1:1 = ', t1, '| len = ', len(t1)
write(*, *) 'tt = ', tt, '| len = ', len(tt)
write(*, *) 't == t1 is ', t == t1
print *
print *, "'ab' sliced by i:i == 'a' and == t and == tt"
write (*, *) list(1)(i:i) == 'a', & ! T
list(1)(i:i) == t, & ! T
list(1)(i:i) == tt ! T
print *
!! both agree on T F result
print *, "direct comparing of 1 char strings"
write(*,*) 'a' == (/ 'a', 'b' /)
write(*,*) (/'a', 'b' /) == 'a'
print *
!! T F
print *, "list(1)(1:1) == (/ 'a', 'b' /)"
write(*,*) list(1)(1:1) == (/ 'a', 'b' /)
print *, "char(1) t ('a') == char(2), dim(2) la ['a', 'b']"
write(*, *) t == la
print *
!! T F
print *, "list(1)(1:1) [char(2) 'a' sliced] == char(2)dim(2) sliced ['a', 'b']"
write(*,*) "1:1 1:1|", list(1)(1:1) == list(:)(1:1)
write(*,*) "i:i 1:1|", list(1)(i:i) == list(:)(1:1)
write(*,*) "i:i i:i|", list(1)(i:i) == list(:)(i:i)
write(*,*) "1:1 i:i|", list(1)(1:1) == list(:)(i:i)
print *
print *, "list(:)(1:1) == X" ! shows the error is someway "propagated" to X
write(*,*) "X is t |", list(:)(1:1) == t
write(*,*) "X is t1 |", list(:)(1:1) == t1
write(*,*) "X is 'a'|", list(:)(1:1) == 'a'
write(*,*) "X is tt |", list(:)(1:1) == tt
print *, "reference: (/ 'a', 'b' /) == tt"
write(*,*) (/'a', 'b'/) == tt
print *
print *, "casting to non parameter"
p = list(:)(1:1)
print *, "p = ", p, "| size(p) = ", size(p)
print *, "p == X"
write(*, *) "X is t |", p == t
write(*, *) "X is t1 |", p == t1
write(*, *) "X is tt |", p == tt
print *
!! same output for g95 and gfortran
print *, "checking diffs between char(1) and char(2)"
write(*,'(A,A)') 'ab', 'cd' !abcd
write(*,'(A,A)') tt, t1 !a a
write(*,'(A,A)') t1, tt !aa
end program test</lang>
:: I also suspect that the difference is that when we are using constant number, the slicing is done at compile time, while when there's a variable that must be evaluated, the slicing is done at runtime and problems arises for the "immutable" nature of the parameter. So as already said a work-around is to remove the parameter attribute...! —[[User:ShinTakezou|ShinTakezou]] 19:45, 27 May 2010 (UTC)
== Simple solution ==
Since there's exactly one permutation missing, there's actually a very simple solution which probably beats all solutions given so far in execution time (unless I've overlooked something, all solutions try to generate all permutations and find them in the list):
* For each position, count how often each letter appears.
* The one which appears one time less than the others is at this position in the missing permutation.
In the given example:
*Position 1: A:6, B:6, C:6, '''D:5'''
*Position 2: A:6, '''B:5''', C:6, D:6
*Position 3: '''A:5''', B:6, C:6, D:6
*Position 4: A:6, B:6, '''C:5''', D:6
Therefore the missing permutation is DBAC. --[[User:Ce|Ce]] 19:49, 16 August 2010 (UTC)
This approach is not very general, but you are right that the task does not need a general solution. For what it's worth here is this approach in J:
<lang j> ,(~. #~ 5 = #/.~)"1 |:data
DBAC</lang>
This was only about 30% faster but it's also a lot shorter -- mostly because I did not bother using any names for the functional part.
--[[User:Rdm|Rdm]] 19:24, 17 August 2010 (UTC)
| |||